Determine the Time Complexity

Question

13) Determine the time complexity of program segment given below:
```
i=n;
while (i>0)
{
k=1;
for (j=1;j<=n; j+=k)<br /> k++;
i = i/2;
}
```

• A. $\mathrm{O}\left(\mathrm{n}^{2}\right)$
  
• B. $\mathrm{O}(\mathrm{n} \cdot \operatorname{logn})$
  
• C. $O\left(\log ^{2} n\right)$
  
• D. $\mathrm{O}(\log n \sqrt{n})$

Answer 1

We have to count the maximum no. of times any instruction is executed- which would be inside the inner most loop. So, we can count the no. of times for loop and while loop execute independently and their product will be our answer. 

for loop:

$ j = 1, 1+2, 1+2+3, ... , 1+2+ ... + l$, where $l$ is the no. of times the loop iterates (for one iteration of while loop). 

From loop exit condition,

$1+2+\dots + l > n$

$\frac{l. (l+1)}{2} > n$

So, $l = \Theta (\sqrt n)$. 

(See, I used $\Theta$ meaning $l$ and $\sqrt n$ have the same order of growth. If LHS has lower or same growth rate we should use big-O and not big-Theta)

while loop

Now, we have to solve the outer while loop. Here $i$ goes like $n, n/2, n/4, \dots n/2^m$, where $m$ is the no. of times the loop iterates. As per the loop exit condition, we can get

$2^m > n$ (which gives an integer value 0)

$\implies m > \log n$

$m = \Theta (\log n)$. 

So, time complexity of code is $m . l = \Theta (\log n \sqrt n)$. 

$\Theta$ means both $O$ and $\Omega$ are also true. Hence option d is correct. 

As per definition of big O, even options A and B are correct though D is the best pick.