Для каждой из следующих функций f найдет простую функцию g такую, что f (n) = Θ (g (n)) (Руководство по проектированию алгоритмов Лекена)

Question

Я выполняю упражнения из Руководства по проектированию алгоритмов Skiena, и я не уверен около 2,30. Не могли бы вы сказать, что мои решения верны? a link to the screenshot of the exercise

1. 4^п
2. п
3. лог (п^20)
4. (0,99)^п

Большое вам спасибо за вашу помощь!

Answer 1

Номера 1 и 4 являются правильными, а 2 и 3 - нет.

• 2: должно быть n log n, потому что log n > (constant).
• 3: должно быть (log n)^10, т.к. log (n^20) = 20 log n, который меньше.