Большой O сокращающегося списка?

Question

Хочу убедиться, что у меня есть это право.

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

Большое значение этого:

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

Это все еще технически O (N)?

Answer 1

Доказательство по индукции:

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

Базовый корпус:

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

Допустим, истина до k для k < n:

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

Доказательство для 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

Таким образом:

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

Answer 2

Если вы решите это, это N-е треугольное число - и, следовательно,

O(N(N + 1) / 2)