Is my method of computing the running time correct?

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?

• i > i is always false, hence the runtime is constant (and the resulting sum is zero) – Hagen von Eitzen Sep 18 '14 at 13:39
• @HagenvonEitzen i was supposed to be 1 there. Sorry. – user6607 Sep 18 '14 at 13:40

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

• How did you know that the number of terms was $\log(N^2)$? I don't get how you did the sum of the series too. Also, did you simply discard the lower order terms to get $\mathcal{O}(N^2)$? – user6607 Sep 18 '14 at 14:53
• @user6607 I have given clarification in my answer. You can check. – user94300 Sep 18 '14 at 14:58
• Hmm...Why is $r$ (in the geometric series formula) equal to $\frac{1}{{2\log{N}}}$? – user6607 Sep 18 '14 at 15:17
• Nevermind. I made a mistake in the edit. It's fixed now. – user6607 Sep 18 '14 at 15:25
• So does $\left(\frac{1}{2}\right)^{2\log n} = \frac{1}{4n}$? – user6607 Sep 18 '14 at 15:29

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.