Асимптоти c Ограничение | Если f = 2 ^ n и g = (2 ^ n + 1), как f = Θ (g)?

Question

Нас просят указать, является ли f = O (g), или f = Ω (g), или и тем, и другим (в этом случае f = Θ (g)).

Чтобы решить большой O, я нашел это простым, просто указав константу C = 1, в этом случае 2 ^ n <= 1 (2 ^ n + 1). </p>

У меня сложилось впечатление, что решить Ω будет невозможно, поскольку нет C, в котором 2 ^ n> = C (2 ^ n + 1).

Изучив решения для проверки моей работы, я обнаружил, что f = Θ (g). Как это могло быть с этой проблемой? Какая константа C могла бы удовлетворить это?

Answer 1

Я не могу сказать, является ли g (n) 2 ^ (n + 1) или (2 ^ n) +1. В любом случае, f (n) - это тета (g (n)).

Предположим, что g (n) = 2 ^ (n + 1). Мы можем переписать это, используя l aws показателей в виде (2 ^ n) (2 ^ 1), что то же самое, что 2 * (2 ^ n). Теперь мы можем просто выбрать c = 1/2, а затем f (n) = c * g (n). Поскольку существует c, для которого функции просто равны, сразу же f (n) = Theta (g (n)).

Предположим, g (n) = (2 ^ n) + 1. Так как f (n) = c * g (n). Если мы выберем c = 1/2, нам нужно найти n0 такое, что 2 ^ n0> = 1/2 2 ^ n0 + 1/2. Мы можем угадать n0 = 1, и мы находим, что это работает; 2 ^ 1> = 1/2 2 ^ 1 + 1/2. Поскольку f (n) также растет быстрее, чем (1/2) 2 ^ n + 1/2, мы закончили.

Answer 2

В чем проблема, если C = 0.1 в качестве примера? Кроме того, вы можете показать запись Theta по пределу этих двух функций, так что lim(f(n)/g(n)), когда n переходит в \infty, равно 1. Это означает, что у нас есть f(n) = \Theta(g(n)).