Running time function for an algorithm with while and for loop

Question

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;
}

• Raphael: " 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.

Answer 1

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ドル$).