0

Want to make sure I have this right.

int n = 20;
while (n > 0) 
   int index = 0
   while (index < n)
      index++
   n--

The Big O of this is:

n + (n-1) + (n-2) + (n-3) + … ++ (n-n)

Is that still technically O(N)?

Jack Bashford
  • 43,180
  • 11
  • 50
  • 79
rygo6
  • 1,929
  • 22
  • 30

2 Answers2

2

Prove by induction:

1 + 2 + 3 + ... + n = n(n + 1) / 2
1 + 2 + 3 + ... + n = O(n^2)

Base case:

n = 1
1 = (1 + 1) / 2
1 = 2 / 2
1 = 1

Assume true up to k for k < n:

1 + 2 + 3 + ... + k = k(k + 1) / 2

Prove true for n = k + 1

1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 1 + 1) / 2

k(k + 1)/2 + (k + 1)          = (k + 1)(k + 1 + 1) / 2

k(k + 1)/2 + 2(k + 1) / 2     = (k + 1)(k + 1 + 1) / 2

(k^2 + k)/2 + (2k + 2) / 2    = (k + 1)(k + 1 + 1) / 2

(k^2 + k + 2k + 2) / 2        = (k + 1)(k + 1 + 1) / 2

(k^2 + 3k + 2) / 2            = (k + 1)(k + 2) / 2

(k^2 + 3k + 2) / 2            = (k^2 + 2k + k + 2) / 2

(k^2 + 3k + 2) / 2            = (k^2 + 3k + 2) / 2

Therefore:

1 + 2 + 3 + ... + n = n(n + 1) / 2
1 + 2 + 3 + ... + n = (n^2 + n) / 2
1 + 2 + 3 + ... + n = O(n^2)
1

If you work it out, it's the Nth triangular number - and therefore:

O(N(N + 1) / 2)
Jack Bashford
  • 43,180
  • 11
  • 50
  • 79
  • 1
    Thank you. That is actually a final answer? Meaning, it doesn't simplify to anything less? It's ultimately O(n^2) isn't it? – rygo6 May 04 '19 at 03:00
  • No, it's not - `O(n^2)` with case of 10 goes to 100, whereas the 10th triangular number is `(10 * 11) / 2 = 110 / 2 = 55`. Big difference. – Jack Bashford May 04 '19 at 03:11
  • Really? The other guy posted below: n(n + 1) / 2 = (n^2 + n) / 2 = O(n^2) That's not correct? – rygo6 May 04 '19 at 03:17
  • 1
    O(N(N+1)/2) = O(N^2) – Matt Timmermans May 04 '19 at 03:17
  • Erm, no - mathematics proves that the two are different: `7 ^ 2 = 49`, and the 7th triangular number is `7(7 + 1) / 2 = (7 * 8) / 2 = 56 / 2 = 28`, formed from `1 + 2 + 3 + 4 + 5 + 6 + 7`. – Jack Bashford May 04 '19 at 03:19
  • 1
    Yes, technically it's `O(n^2)`.See this [post](https://stackoverflow.com/questions/29954109/why-do-we-ignore-co-efficients-in-big-o-notation). But we all get the point. – hackape May 04 '19 at 03:22
  • By [definition](https://en.m.wikipedia.org/wiki/Big_O_notation), `O(n(n + 1) / 2)`, `O(n^2 / 2)` and `O(n^2)` are all correct. You can claim `O(7 * n^2 + 1024)` is correct too. But by convention, we pick `O(n^2)`. – hackape May 04 '19 at 03:36