Простой Big O с lg (n) доказательством

Question

Я пытаюсь угадать и доказать Большой О для:

f (n) = n ^ 3 - 7n ^ 2 + nlg (n) + 10

Я полагаю, что большой O равен n ^ 3, так как это термин с наибольшим порядком роста

Однако у меня проблемы с доказательством. Вот моя неудачная попытка:

f(n) <= cg(n)
f(n) <= n^3 - 7n^2 + nlg(n) + 10 <= cn^3 
f(n) <= n^3 + (n^3)*lg(n) + 10n^3 <= cn^3
f(n) <= N^3(11 + lg(n)) <= cn^3

so 11 + lg(n) = c

Но это не может быть правильно, потому что с должно быть постоянным. Что я делаю не так?

Answer 1

Для любой базы b мы знаем, что всегда существует n0 > 0 такой, что

log(n)/log(b) < n всегда n >= n0

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

n^3 - 7n^2 + nlg(n) + 10 <<code>n^3 - 7n^2 + n^2 + 10 когда n >= n0.

Вы можете решить оттуда.

Answer 2

По вашему вопросу доказательство O (n ^ 3) должно выглядеть примерно так:

f(n) <= n^3 + 7n^2 + nlg(n) + 10 for (n > 0)
f(n) <= n^3 + 7n^3 + nlg(n) + 10 for (n > 1)
f(n) <= n^3 + 7n^3 + n*n^2 + 10  for (n > 2)
f(n) <= n^3 + 7n^3 + n^3 + 10  for (n > 2)
f(n) <= n^3 + 7n^3 + n^3 + n^3 for (n > 3)
f(n) <= 10n^3 for (n > 3)

Следовательно, f (n) равно O (n ^ 3) для n> 3 и k = 10.