Complexity of for loop

Question

I found this on the web :

for (i=1; i<=n*n; i++)
    for (j=0; j<i; j++)
        sum++;

Exact # of times sum++ is executed:

Sum{i=1, i=n^2}= (n^2)*((n^2)+1)/2 ∈ Θ(n^4)

End of quote.

While I agree with the result, it seems to me this takes only the first loop in account, the one on i, not the one on j. In other words, mathematically we would have the same result with the code :

for (i=1; i<=n*n; i++)
    sum++;

i.e, still : Sum{i=1, i=n^2}= (n^2)*((n^2)+1)/2 ∈ Θ(n^4) while this code is clearly Θ(n^2) (it runs exactly n^2 times)

Can someone explain me what I'm missing ?

Answer 1

Assuming a constant number of operation c being done while incrementing the value.

Answer 2

Without j it would be Count{i=1, i=n^2}, not Sum{i=1, i=n^2}, so it will deduce to n*n