Use the limit rule to find Big Oh characterization of for loop

Question

Find Big Oh characterization in terms of n, the professor says to use the limit rule for big Oh which says
f(n) = O(g(n)) means f(n) "≤" g(n) => lim n->inf f(n)/g(n) = c where c is 0< c < inf

The algorithm is
s←0
for i←1 to n² do
    for j ← 1 to i do
        s←s+i

I think the answer would be O(n³) because we have n² for the first loop and n for the nested loop and then you multiply them together because its nested. But Im not sure where the limit rule comes into play.

Answer 1

You would be wrong. The inside loop does not run $n$ times for each $i$.

It is unclear whether you are looking for $s(n)$ or the number of additions.

Exactly, $s(n) = \dfrac{n^2(n^2+1)(2n^2+1)}{6}$ while the number of additions is $\dfrac{n^2(n^2+1)}{2}$, neither of which is $O(n^3)$.