Правила Big O - Вопрос

Question

Если у меня есть следующее решение для замкнутой формы для рекуррентного отношения, как я могу упростить его при больших O:

f (n) = 3 ^ n + n.9 ^ n

Я бы рискнул предположить:

f (n) является членом O (9 ^ n) -> Не уверен, верно ли это? Может кто-нибудь, пожалуйста, дайте мне знать, как упростить приведенное выше уравнение при больших O, а также указать, какое правило вы использовали ...

Заранее спасибо

Answer 1

http://en.wikipedia.org/wiki/Big_O_notation

Если f (x) является суммой нескольких слагаемых, то значение с наибольшим темпом роста сохраняется, а все остальные опускаются.

Итак O(n * 9^n), предполагая, что с n.9^n вы имели в виду n * 9^n.

Answer 2

Простые отношения, которые вам помогают, это:

O(1) < O(log(N) < O(N^Epsilon)<O(N)<O(N logN)<O(N^c)<O(c^n)<O(n!)<O(n^n)

для c> 1 и 0 <Эпсилон <1. </p>

См. большой O в вики для лучшего понимания