3
$\begingroup$

I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, int i=n and int s=0.

Also, I know that the while loop is represented by $\lfloor \log_2n \rfloor + 1$, but the for loop depends on the value of $i$ which decrements by half.

So, the first time the for loop performs $n$ times, the second time the for loop performs $n/2$ times, and so on. How can I represent this behavior?

I suppose that, at the end, the result is the product of both behaviors.

int i = n; int s = 0; 
while(i > 0) { 
    for(j = 1; j <= i; ++j) s++; 
    i /= 2;
}
$\endgroup$
  • $\begingroup$ " the while loop is represented by ..." -- that statement does not make too much sense. "at the end, the result is the product of both behaviors" -- not quite, except in simple cases. See our reference question on how to analyse such things; you can also search runtime-analysis+loops. $\endgroup$ – Raphael Jul 13 '15 at 9:58
2
$\begingroup$

For each value of $i$, the inner loop runs $i$ times, and so the running time of the body of the outer loop with a given value i is in $\Theta(i)$. The values of i, as you mention, are $n, \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \cdots, 1$, and so the overall running time is $$ \Theta(n + n/2 + n/4 + \cdots + 1) = \Theta(n). $$ Here we use the fact that the infinite series $1 + 1/2 + 1/4 + \cdots$ converges (to $2$).

$\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.