Пример обозначения Big O Показать, что N ^ 2 не O (n)

Question

Показать, что n ^ 2 не O (n)

f(n)=n^2
g(n) = n
c = 1
n_0=2

n^2 <= 1*n for all n_0 >= 2
4 <= 2 
4 is not less than or equal to 2. Therefore, n^2 is not O(n). 

Мне нужно показать, что с этим работает NO c, однако с c 2, с n из 2 сработает. Как п ^ 2 не п?

Answer 1

Предположим, что n² находится в O (n) .

Тогда должно быть c и n₀ , таких что для всех n ≥ n₀ , n² ≤ c * n ( по определению обозначения O).

Пусть k = max (c, n₀) + 1 . По указанному выше свойству имеем k² ≤ c * k (начиная с k> n₀ ), из которого следует, что k ≤ c .

Однако, k> c по построению. Это противоречие.

Поэтому наше предположение неверно, и n² не может быть в O (n) .