0
$\begingroup$

A double loop is given:

int sum = 0;
for (int i = 0; i < N*N; i++)
    for (int j = i; j < N; j++)
        sum++;

My analysis: The inner loop runs $n$ times the first iteration, then $n-1$, $n-2$, $n-3$, $n-4$ until it gets to $n-n$ which is zero. This is a series summation which is expressed as: $$\sum_{i=0}^n \frac{1}{2}(n(n+1))= \frac{1}{2}(n^2+n)= \frac{1}{2}n^2 + \frac{1}{2}n$$ Discarding lower terms and constants give $\mathcal{O}\left(\frac{1}{2}n^2\right) \rightarrow \mathcal{O}(n^2)$.

The outer loop is executed $n^2$ times. Multiplying by the inner loop gives $\mathcal{O}(n^4)$. Is this right?

Update: Now I think the actual answer is $\mathcal{O}(n^2)$ because the inner loop is only executed half the times of the outer loop.

$\endgroup$
  • $\begingroup$ You're factoring in the outer loop twice - you effectively factor it in once when you compute your (series) summation, but then multiply by it as well. $\endgroup$ – Steven Stadnicki Sep 18 '14 at 17:23
  • $\begingroup$ @StevenStadnicki I just realized that. See my update at the bottom. Is this correct? $\endgroup$ – user6607 Sep 18 '14 at 17:24
  • $\begingroup$ You're much more on the right track - though for a formal analysis I would split the outer loop into the two pieces $0\leq i\lt N$ and $N\leq i\lt N^2$. (Note that you still run the inner loop over the latter case, even though you don't execute any statements within it.) $\endgroup$ – Steven Stadnicki Sep 18 '14 at 17:25
2
$\begingroup$

By splitting the outer loop into $0\leq i\leq N-1$ and $N\leq i\leq N^2-1$ (because the code inside the inner loop isn't executed at all for $i\geq N$, but still costs $\mathcal{O}(1)$ time to do) we obtain: $$\begin{align} \sum_{i=0}^{N-1}\sum_{j=i}^{N-1}1+\sum_{i=N}^{N^2-1}1&=\sum_{i=0}^{N-1}(N-1-i+1)+N^2-1-N+1\\ &=\sum_{i=0}^{N-1}N-\sum_{i=0}^{N-1}i+N^2-N\\ &=N^2-\frac{(N-1)N}{2}+N^2-N\\ &=\mathcal{O}(N^2). \end{align}$$

$\endgroup$
  • $\begingroup$ Is this a quicker way to do what I did? $\endgroup$ – user6607 Sep 18 '14 at 19:13
  • $\begingroup$ I'm not sure whether it is quicker, but I find it easier to apply, since you can just interpret every loop as a sum. If you had several nested loops, it's usually quite easy to convert them to an expression with summations. Also, you can just work from the outer loop to the inner loop rather than the other way around. It's probably just preference, but I find this method easier to understand and less subject to errors. $\endgroup$ – Joffysloffy Sep 18 '14 at 19:17
  • $\begingroup$ Is one expected to calculate the function by hand? Because I wouldn't be able to do so for this example. $\endgroup$ – user6607 Sep 18 '14 at 19:23
  • $\begingroup$ Do you mean the first expression in my answer? That's just directly deduced from the code you provided. $\endgroup$ – Joffysloffy Sep 18 '14 at 19:25
  • $\begingroup$ How am I supposed to calculate a summation like that (by hand)? I wouldn't know where to start. $\endgroup$ – user6607 Sep 18 '14 at 19:42

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.