Упрощение с использованием выражения Big Theta

Question

Я изучаю алгоритмы и сейчас пытаюсь понять нотацию big-O. Один из вопросов упражнения выглядит как log (n) + 10 ^ 6n ^ 5000 + 3 ^ n . Задача состоит в том, чтобы упростить выражение с помощью expression-выражения. Как я понимаю, он просит сказать Θ для этого выражения, что означает, что оно выглядит так: log (n) + 10 ^ 6n ^ 5000 + 3 ^ n = Θ (n ^ 5000) ?

Answer 1

Да. Но результат неправильный! Это должно быть \Theta(3^n), так как 3^n является экспоненциальной функцией и растет быстрее, чем полиномиальная функция, такая как n^{5000}. Кроме того, вы можете думать о пределе данной функции более 3^n, когда n уходит в бесконечность.