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

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

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