Доказательство сложности

Question

Я бы доказать следующий пример:

n^k = O (c^n) for every k and c>1

Заметно, что полиномиальная функция растет быстрее, чем экспоненциальная функция. Мы пытаемся найти k0> 0, удовлетворяющее условию

fn > = k0 * g(n)

Чем

n^k <= k0 * c^n
log(n^k) <= log (k0 * c^n)
log(n^(k/n)) <= log (k0 * c)
k0 >= 1/c*n^(k/n)

Итак, k0> 0, положительно и достаточно мало, а значение c не имеет значения ... Это нормально?

Answer 1

log(n^k) <= log (k0 * c^n)
k log n <= log k0 + n log c

k log n - n log c <= log k0
log (n^k) - log (c^n) <= log k0
log ((n^k) / (c^n)) <= log k0 | expo
(n^k) / (c^n) <= k0
n^k <= k0 * c^n

=> n^k = O(c^n)

Ваш шаг 3 кажется неправильным, по крайней мере, я не понимаю, откуда вы это взяли. Ваше заключение также, кажется, не подтверждает то, о чем просили.