# Running time function for an algorithm with while and for loop

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

• " 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. – Raphael Jul 13 '15 at 9:58

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