1

I'm looking at an algorithm and trying to break it down and come up with the Big O notation for it. However, I am unable to deduce why it is O(n^2)

I can see that the outer loop goes to N, but the inner loop is throwing me off

int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
}

Does anyone know how I can best approach these kinds of questions, if they were to pop up in an interview? I want to get better at analyzing algorithms

blazerix
  • 770
  • 4
  • 8
  • 24
  • 1
    Hint: You can find a formula in terms of `N` for exactly how many times the assignment to `a` is evaluated. – aschepler May 18 '19 at 01:48
  • Possible duplicate of [Big O: How to determine runtime for a for loop incrementation based on outer for loop?](https://stackoverflow.com/questions/41407714/big-o-how-to-determine-runtime-for-a-for-loop-incrementation-based-on-outer-for) – Matt Timmermans May 18 '19 at 01:54
  • You can check this question there are some good explanations about Big O notation:[How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm?rq=1) – fatihgonen May 18 '19 at 03:22
  • Also while it is different from your question, I found that working with proofs with induction helped me understand big O notation better, since it has similarities in how you think about the problem. If you're interested in math and proofs you can check out proofs with induction on google. Kinda makes you think about the notation-type like melpomene explained in his answer. – Riley Carney May 20 '19 at 17:26

2 Answers2

4

The outer loop iterates from 0 to N-1.

The inner loop iterates from N down to i+1.

That means in the first iteration of the outer loop, the inner loop takes N steps. In the second iteration of the outer loop, the inner loop takes N-1 steps. In the third iteration of the outer loop, the inner loop takes N-2 steps. ... This continues until the last iteration of the outer loop, where the inner loop takes 1 step.

The total number of steps is therefore N + (N-1) + (N-2) + ... + 2 + 1, or (rearranged) 1 + 2 + ... + (N-1) + N. This sum is equal to N * (N+1) / 2 (see here for details), which expands to 0.5 * N^2 + 0.5 * N. Ignoring lower powers and constant factors means this is in O(N^2).

melpomene
  • 84,125
  • 8
  • 85
  • 148
3

If you're a visual person, you can think of the outer loop as rows, and the inner loop as columns. For each iteration of the outer loop, the number of iterations (columns) in the inner loop decreases by 1.

Presenting this visually, you get:

* * * * * 
  * * * * 
    * * * 
      * * 
        *

This is half a square (triangle), so approximately (n^2)/2, which is O(n^2).

Eric
  • 730
  • 4
  • 16