# Loop runtime question

I had an exam today and I feel that I did pretty well, except I could not for the life of me figure out what appears to be an unbelievably simple question.

We were asked to give theta notation run times for a few programs(with input size n), and this was one of them:

``````int sum = 0;
for int i = 0; i < n; i++
for int j = 0; j < i; j++
sum++
``````

So I know iterating from 0 to n on both loops would render a O(n2) run time... but with the second loop only iterating to the first loop control variable, I would assume it must be faster... because the second loop never even reaches n iterations until the very last loop-through?

I'm gonna freak out if its O(n2) and I over thought this...

• Walk through `n = 3`. Then through `n = 4`. – Oded Nov 6 '14 at 21:47
• 1st loop nothing happens, j isnt less than i – Joey Hanlon Nov 6 '14 at 21:55
• 2nd loop i is 1, j = 0 loops through 1 time – Joey Hanlon Nov 6 '14 at 21:56
• 3rd, i is 2 and j loops through at 0 then 1 – Joey Hanlon Nov 6 '14 at 21:56
• Can you figure out a formula for how many times the j loop would execute? Based on n? – Oded Nov 6 '14 at 21:58

The complexity class is `O(n²)`.

## Visual explanation

Imagine a `n·n` square which lists all the values `j` takes on. We remove the diagonal (which has `n` entries) and the upper right half because `j` will never be larger or equal to `i`. We are then left with an area of `(n² - n)/2`.

`````` i  | values of j     | no of j values
----+-----------------+---------------
0  | · · · · ·  ⋯  · |  0
1  | 0 · · · ·  ⋯  · |  1
2  | 0 1 · · ·  ⋯  · |  2
3  | 0 1 2 · ·  ⋯  · |  3
4  | 0 1 2 3 ·  ⋯  · |  4
:  | : : : :    :  : |  :
n-1 | 0 1 2 3 ⋯ n-2 · | n-1
=====
SUM: (n² - n)/2
``````

## Mathematical explanation

The outer loop executes `n` times, the inner loop `i` times. We can write the number of executions of the inner loop body as `∑mi=1 i` with `m = n-1`. The sum of all natural numbers up to including `m` can also be written as `m·(m + 1)/2` (the formula for triangular numbers), which leads to `n(n-1)/2`.

## Conclusion

Using either method, we can determine that the nested loops have a complexity of `O((n² - n)/2) = O(n²)`.

I'm gonna freak out if its O(n2) and I over thought this...

Don't freak out -- too much.

The outer loop will execute n times. The inner loop will execute an average of about (n/2) times. This results in a total of n2/2 evaluations - or in more precise notation, runtime of O(n2).

Also this is pretty easy to verify by writing a short/simple program.

For this particular situation, how you can remember it: You could rewrite it as

``````for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (j < i)
do_some_stuff ();
``````

The loop now clearly executes n^2 times. do_some_stuff executes only if j < i. Since either j < i or j > i (with the rare case j == i), j < i is true about half the time, and do_some_stuff is executed about n^2 / 2 times.

Now say you have a loop like that with four variables i, j, k, l. And you figure out n^4 iterations, but do_some_stuff is executed only if i < j < k < l. Since four numbers can be arranged in 24 different ways, i < j < k < l happens about one out of 24 times, so do_some_stuff is executed n^4 / 24 times.

You can just cheat: Count how often something happens and print the numbers out. Put them into a spreadsheet. For example in your case print sum, then in a spreadsheet enter n, sum, sum / n, sum / n^2, sum / n^3, sum / n^4. You will find that one of these tends not to change much when n gets large.