Is my method of computing the running time correct?

Question

Okay, so this is the code for which I need to compute the running time:

int sum = 0;
for (int i = N*N; i > 1; i /= 2)
    for (int j = 0; j < i; j++)
        sum++;

So the first one goes from $N^2$ and keeps dividing $i$ in two until it is a multiple of $N^2 \leq 1$. So I would say this is $\log_2{N^2}$, correct? Or can it be simplified to $\log_2{N}$?

Assuming the first one is correct, the second inner loop runs $N^2$ times the first iteration of the $i$ loop, then $\frac{N^2}{2}$ the second, then $\frac{N^2}{4}$, $\frac{N^2}{6}$, $\frac{N^2}{8}$ and so on. It seems to me to be logarithmic running time.

So multiplying the two together gives $\log_2{N^2} * \log_2{N^2} = \log_2^2{N^2}$

I know this can't be correct as none of the multiple choice gives that, so what is wrong with how I am evaluating the loops?

Answer 1

The statementsum++; shall run following number of times:

\begin{align*} &= N^2 + \frac{N^2}{2} + \frac{N^2}{4} + ... + \frac{N^2}{2^k}\\ &= N^2 * \left( 1 + \frac{1}{2} + \frac{1}{4} + ... + \frac{1}{2^k} \right) \end{align*}

If the number of terms in this series is $k$, then we have:
$2^k = N^2$. (because the terms are halved till we reach zero).
Hence the number of terms in the above expression = $\log(N^2) = 2\log(N)$.

This is a geometric series with common factor $\left(\frac{1}{2}\right)$. Applying the geometric series sum formula:

\begin{align*} \text{Hence sum of series} &= N^2 * \frac{1 - \left(\frac{1}{2}\right)^{2\log N}}{\frac{1}{2}}\\ &= N^2 * \frac{1 - \frac{1}{4N}}{\frac{1}{2}}. \end{align*}

Neglecting the lower order terms:
Hence according to me the order of complexity = $\mathcal{O}(N^2)$

Answer 2

You are correct that the outer loop "keeps dividing $i$ in two". So if $i$ starts at $N^2,$ the next two values are $\frac{N^2}{2}$ and $\frac{N^2}{4},$ just as you wrote--but the next value after $\frac{N^2}{4}$ is $\frac{N^2}{8},$ not $\frac{N^2}{6}.$

You should be summing a geometric series rather than a harmonic series. Also, there is that factor of $N^2$ in each loop's running time; don't forget that.