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

Question

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.

Answer 1

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