# Big O of shrinking list?

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

On

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

``````O(N(N + 1) / 2)
``````
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)
``````