# Does this loop run in $\mathcal{O}(n^4)$ time?

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.

• 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. – Steven Stadnicki Sep 18 '14 at 17:23
• @StevenStadnicki I just realized that. See my update at the bottom. Is this correct? – user6607 Sep 18 '14 at 17:24
• 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.) – Steven Stadnicki Sep 18 '14 at 17:25

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}