Algorithms Sample Questions | Set 3 | Time Order Analysis

1. θ( n*log(n) )
2. θ( n² )
3. θ( n )
4. θ( n*log²(n) )
5. θ( n²*log²(n) )

• This is obvious that for any k greater than √ n, each log_kn should be less than log_√nn = 2, while more than log_nn = 1. In mathematic language:
  1. A hint on UPPER boundary, for k > √ n:

  2. A hint on LOWER boundary, for k > √ n:

• Besides that, as the base of a logarithm increases, its value decreases; so none of the terms resulted from expansion of the first sigma can be more than the first ter, log₂n, nor can be less than the last one, which is log_√nn; in other sentences,
  1. Another hint on UPPER boundary, but this time for k < √ n:

  2. Another hint on LOWER boundary, but this time for k < √ n:

1. Lower boundary:

2. Upper boundary:

C PROGRAM: Input n of type integer
  for(i= 2; i<n; i=i+1)
   for(j = 1; j < n; j= j * i)
    // A line of code of Θ(1)

1. θ( n )
2. θ( n*log(n) )
3. θ( n² )
4. θ( n*log²log(n) )
5. θ( n²*log²(n) )

1. The first code line, t₁(n), is:   for(i= 2; i<n; i=i+1) // it runs (n – 2) times; so the time complexity of this line is of θ(n)
2. The second code line, t₂(n) is:    for(j = 1; j < n; j= j * i) // log₂ⁿ + log₃ⁿ + … + log_n-1ⁿ = Σlog_iⁿ ∈ Θ( n ) in according to PREVIOUS QUESTION of this article (Refer to Question 1)
3. The third code line, t₃(n) is:     //A code line of Θ(1) :: Inside loops, so its order time is as the same as that of previous line, which is of Θ( n )

1. 1
2. 2
3. 3
4. 4
5. 5

1 " title="Rendered by QuickLaTeX.com" height="29" width="429" style="vertical-align: -9px;">

• case 1: This case happens the recursion tree is leaf-heavy (the work to split/recombine a problem is dwarfed by subproblems.)

  0, f(n) \leq n^{log_{b}{a- \epsilon} } \Rightarrow T(n) \in \theta (n^{lob_{b}{a}}) " title="Rendered by QuickLaTeX.com" height="31" width="482" style="vertical-align: -7px;">

• case 2: This case occurs when the work to split/recombine a problem is comparable to subproblems.

• case 3: This case takes place when the recursion tree is root-heavy (the work to split/recombine a problem dominates subproblems.)

  0, f(n) \geq n^{log_{b}{a + \epsilon} } \Rightarrow T(n) \in \theta (f(n)) " title="Rendered by QuickLaTeX.com" height="31" width="472" style="vertical-align: -7px;">

• -1, " title="Rendered by QuickLaTeX.com" height="24" width="104" style="vertical-align: -5px;">

 C PROGRAM: inputs m and n of type integer 
  for(i= 1; i<= n; i=i+1) : n
   for(j = 1; j <= m; j= j * 2)
    for(k = 1; k <= j; k= k+1)
     \\ A code line of Θ(1)

1. θ( n * m*(m+1)/2 )
2. θ( n*m + n*log²(m) )
3. θ( m³ )
4. θ( n² )
5. θ( n²*log²(n) )

1. for(i= 1; i<= n; i=i+1) // It runs n times

2. for(j = 1; j <= m; j= j * 2) // iterates log₂(m) times, and it is inside another loop which multiply it n times

3. for(k = 1; k <= j; k= k+1) // It runs 2 + 4 + 8 + … + 2^log(m) times
   This is also inside an outer loop, first “for” loop, which itself iterates n times

4. \\A line of code of Θ(1) The same as previous line, Θ( m*n )

Tmp = -1;
  For r= 1 to N
   For S = 1 to V[r]
    Tmp = Tmp + 20;

1. O( N + 2*N*P )
2. O( N * P )
3. O( N² )
4. O( P² )
5. O( 2*P + N )

1. Each V[r] can take any integer value (even zero or negative ones), but it doesn’t matter as all negative values will lead to no execution of the second loop in programming languages like C. However, in programming languages, it is allowed to count down-to (or to iterate over) negative numbers, but the algorithms are not being analyzed depends on programming languages, and the analysis is just based on the algorithm itself. What to say for sure is the information that is given in the question; so a shrewd action is to consider the absolute value of |V[r]| and also to use O() notation in order to get rid of being stuck. Otherwise, it has to be said that the program runs at least as much as the time needed for just execution of the first loop, or Ω(N)
2. Although the running time order of this program does not seem to depend on two variables, but there is no more information for further analysis which is needed to compare P and N; so the asymptotic complexity depends on the values of both P and N; in other words, there is T(N, P) complexity function instead of T(N).
3. The O() notation defines a looser boundary than the tight boundary specified by &theta() notation; Therefore, the sum of θ() and O() would be of O() type. In this problem, the total time complexity of the program, which is the sum of all code lines complexities, θ(1) + θ(N) + O( P ) + O( P ), belongs to set O( 2 * P + N + 1 ) or O(2*P + N).

Source:

1. A compilation of Iran university exams (with a bit of summarization, modification, and also translation)