Big O of shrinking list?

Asked by At

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)?

2 Answers

1
Jack Bashford On

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

O(N(N + 1) / 2)
2
Jabari Dash On

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)