0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.