5

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
  • 2
    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
19

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²).

5

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.