Compute the worst case time complexity of the following algorithm, for i = 1 to n do for j = i to n^2 do print (i, j).

Question

for i = 1 to n do 

    for j = i to n^2 do 

            print (i, j).

So here is what I've got

$\sum_{i=1}^n \ \sum_{j=i}^{n^{2}} \ $

$C\sum_{i=1}^n \ \sum_{j=i}^{n^{2}} 1\ $

$C\sum_{i=1}^n \ (n^{2}-i+1) $

$C\sum_{i=1}^n \ n^{2} \ - \sum_{i=1}^n \ i \ + \sum_{i=1}^n \ 1\ $

Which becomes

$n^{3} + \dfrac{n(n+1)}{2} + n$

And since the term with the highest exponent dominates

$O( n^3)$

Now I'm a complete beginner, and I came up with this solution by going over my notes.

Was this the correct solution? If not how would I solve this problem?

Answer 1

That's exactly how I would do it.

Looks fine to me.