Не могу рассчитать скорость роста функции

Question

Здравствуйте, я пытаюсь решить вопрос на изображении выше, но я не могу.

В частности, мой вопрос о C(n) на изображении, в конце я получил "7logn + n^(1/3)".

мы знаем, что левая сторона знака +, "7logn<=n для всех n>7 (свидетель c=1, k=7)", и правая сторона знака +, "n^(1/3)<=n",

Обе стороны между знаком + с моей точки зрения - это O(n), и, таким образом, весь C(n) - это O(n).

Но почему ответ Big-theta(n^1/3)?

Answer 1

Это верно только в том случае, если log является логарифмом основания 2 (тогда log (8) = 3, потому что 2 ^ 3 = 8).

8 ^ (log (n) / 9) = (8 ^ log (n)) ^ (1/9) = (n ^ log (8)) ^ (1/9) = (n ^ 3) ^ (1 / 9) = n ^ (3 * 1/9) = n ^ (1/3)

n ^ (1/3) совпадает с 3-м корнем n.

Это O(n ^ (1/3)), а не O (log (n)), потому что первый термин растет быстрее:

Предел n к бесконечности log (n) / (n ^ (1/3)) равен 0. Если бы вам пришлось переключать выражения, чтобы получить 0, то другое будет расти быстрее. Например, n + log (n) будет O(n), потому что n растет быстрее, не путать с n * log(n), который равен O(n * log(n)).