Big-O Time Complexity of nested for loops [duplicate]

Question

My gut tells me the time-complexity of the following code is simply O(n^2). However, I'm not convinced, thinking it could possibly be O(n^3):

cin >> n;
sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n * n; j++)
        sum++;

Can anyone provide a distinction, and why?

Thanks in advance.

See also runtime-analysis+loops. And, important, here; $O(n^2)$ and $O(n^3)$ are not mutually exclusive, in fact $O(n^2) \subset O(n^3)$. You want to talk about $\Theta$. — Raphael, Commented Mar 2, 2015 at 0:03

Yuval Filmus · Accepted Answer · 2015-03-01 22:12:57Z

2

Hint: What is the value of sum at the end of the code, as a function of $n$? If it is $s$ then the fifth line must have been run exactly $s$ times.

answered Mar 1, 2015 at 22:12

Yuval Filmus

279k27 gold badges316 silver badges512 bronze badges

$\begingroup$ So, I ran the program and input 5, and the value of sum was 5^3 = 75. Does this mean it is O(n^3) ? Still not convinced. $\endgroup$
– user29291
Commented Mar 1, 2015 at 22:20
$\begingroup$ Make sure that you understand the concept of running time. If a line is run $s$ times then the running time is at least $s$. $\endgroup$
– Yuval Filmus
Commented Mar 1, 2015 at 22:22
$\begingroup$ Thank you. I mistyped in my previous comment, should be 125 instead of 75. $\endgroup$
– user29291
Commented Mar 1, 2015 at 22:29

Add a comment |

1 Answer 1