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

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?

  • $\begingroup$ i > i is always false, hence the runtime is constant (and the resulting sum is zero) $\endgroup$ – Hagen von Eitzen Sep 18 '14 at 13:39
  • $\begingroup$ @HagenvonEitzen i was supposed to be 1 there. Sorry. $\endgroup$ – 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)$

  • $\begingroup$ 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)$? $\endgroup$ – user6607 Sep 18 '14 at 14:53
  • $\begingroup$ @user6607 I have given clarification in my answer. You can check. $\endgroup$ – user94300 Sep 18 '14 at 14:58
  • $\begingroup$ Hmm...Why is $r$ (in the geometric series formula) equal to $\frac{1}{{2\log{N}}}$? $\endgroup$ – user6607 Sep 18 '14 at 15:17
  • $\begingroup$ Nevermind. I made a mistake in the edit. It's fixed now. $\endgroup$ – user6607 Sep 18 '14 at 15:25
  • $\begingroup$ So does $\left(\frac{1}{2}\right)^{2\log n} = \frac{1}{4n}$? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.