[Math] Complexity for nested for loop with logarithmic runtime

algorithmsasymptoticsgeometric-progressions

I am trying to understand the time complexity for following simple code.

1. int sum = 0;
2. for (int n = N; n > 0; n /= 2)
3.   for(int i = 0; i < n; i++)
4.      sum++;

I can see outer loop runs for $logN$ times. For each iteration inner loop runs for $N$ times (where $N$ is the $n$ for that iteration). This seems to be $O(NlogN)$.

But I could not understand why this is true.

If I try to calculate how many times each line is getting executed, I found the following.

Total complexity = $\sum_{i=1}^4 t_i$ where $t_i$ is the number of times line $i$ gets executed.

$t_2$: $logN$ (as each time it is getting reduced by half) => $\frac{N}{2^k}=1$ where $k=t_i=logN$

$t_3$: Total number of times it runs is $\frac{N}{2^0}+\frac{N}{2^1}+\frac{N}{2^1}+……+\frac{N}{2^k}$ where $k=logN$. Common out $N$, we have $N(\frac{1}{2^0}+\frac{1}{2^1}+\frac{1}{2^1}+……+1)$. I can see the Geometric progression. But if I solve it, I cannot get get what I want i.e., $NlogN$.

$t_4$: Should be similar to $t_3$

What am I missing here? can any one help me understand this?

Best Answer

\begin{align*} N\left( \frac 1{2^0}+\ldots+\frac 1{2^k} \right) &= N\sum_{i=0}^k \left(\frac 12\right)^i =N\frac{ 1 -\left(\frac 12\right)^{k+1} }{ 1 -\frac 12 } =2N-\frac N{2^k} \approx 2N-1 =\mathcal O(N) \end{align*} Your overall complexity is linear. On a side note, this is an illustration of Zeno's paradox. Imagine you race 100m, and every minute you only run half the distance to the finish line. You never finish the race, but assuming you somehow get to infinity the total distance you've run is 100m. This sum is the same thing.

Edit: completely unrelated but mathjax has a \log N commmand which makes a much nicer output: $\log N$

Related Question