How to derive time complexity of following method.

Question

I have one algorithm for which I have to find time complexity of number of time x=x+1 is executed:

j=n;
while(j>=1){
  for i=1 to j
    x =x+1
  j=j/2
}

What I am doing is : while loop will run for logN times and so as for loop.

That's why T(n) = (logN) * (logN)

Am I correct?

Answer 1

On the first iteration of the while loop, notice that $j$ is still equal to $n$, and therefore the for loop will execute $n$ times. That is, we already have executed x=x+1 $n$ times. For large $n$, we find that $n > (\log n)^2,$ so unfortunately right away we know the time complexity cannot be $(\log n)\cdot(\log n).$

Sometimes it's better to just count the innermost loop. In this case the first time the for loop runs, it iterates $n$ times. The next time the for loop starts, it iterates $n/2$ times (rounded down), the time after that iterates $n/4$ times (rounded down), and so forth until the last time through, when it iterates just once (because $j=1$).

So to find the number of times we execute x=x+1 altogether, just add up the iterations for each time the for loop starts. These are at most:

$$n + \frac n2 + \frac n4 + \frac n8 + \ldots + 1.$$

The exact answer will be a little less when $n$ is not a power of $2,$ but not too much less. It is easy to add up this total and to find its asymptotic form.