Is 2 ^ (2n) = O (2 ^ n)

Question

Is <strong>2<sup>(n+1)</sup> = O(2<sup>n</sup>)</strong>?

Я считаю, что это правильно, потому что n+1 ~= n.

---

Is <strong>2<sup>(2n)</sup> = O(2<sup>n</sup>)</strong>?

Похоже, что он будет использоватьта же логика, но я не уверен.

Answer 1

Первый случай, очевидно, верен - вы просто убираете постоянную

Текущие ответы на вторую часть вопроса, выглядите для меня как мах, поэтому я попытаюсь дать правильное математическое объяснение.Предположим, что вторая часть верна, тогда из определения big-O вы получите:

, чтоявно неверно, потому что нет такой константы, которая удовлетворяла бы такому неравенству.

Answer 2

Заявка: 2 ^ (2n)! = O (2 ^ n)

Доказательство от противного:

1. Предположим: 2 ^ (2n) = O (2 ^ n)
2. Это означает, что существует c> 0 и n_0 st 2 ^ (2n) <= c * 2 ^ n для всех n> = n_0
3. Деление обеих сторон на 2 ^ n,мы получаем: 2 ^ n <= c * 1 </li>
4. Противоречие!2 ^ n не ограничено константой c.

Следовательно, 2 ^ (2n)! = O (2 ^ n)

Answer 3

Я предполагаю, что вы просто оставили запись O () на левой стороне.

O (2 ^ (n + 1)) - это то же самое, что O (2 * 2 ^ n),и вы всегда можете извлечь постоянные коэффициенты, так что это то же самое, что O (2 ^ n).

Однако постоянные факторы - это единственное, что вы можете извлечь.2 ^ (2n) можно выразить как (2 ^ n) (2 ^ n), а 2 ^ n не является константой.Итак, ответ на ваши вопросы - да и нет.

Answer 4

Обратите внимание, что

2<sup>n+1</sup> = 2(2<sup>n</sup>)

и

2<sup>2n</sup> = (2<sup>n</sup>)<sup>2</sup>

Оттуда либо используйте известные вам правила записи Big-O, либо используйте определение.

Answer 5

Чтобы ответить на эти вопросы, вы должны обратить внимание на определение обозначения big-O. Поэтому вы должны спросить:

существует ли константа C такая, что 2^(n+1) <= C(2^n) (при условии, что n достаточно велико)?

То же самое относится и к другому примеру: существует ли какая-либо константа C такая, что 2^(2n) <= C(2^n) для всех n достаточно большой?

Работайте над этим неравенством, и вы будете на пути к решению.

Answer 6

2 ^{n + 1} = O (2 ⁿ ) , потому что 2 ^{n + 1} = 2 ¹ * 2 ⁿ = O (2 ⁿ ).Предположим, что 2 ²ⁿ = O (2 ⁿ ). Тогда существует постоянная c, такая, что для n за пределами n ₀ , 2 ²ⁿ <= c 2 <sup>n .Разделив обе стороны на 2 ⁿ , получим 2 ⁿ 0 , которые могли бы сделать это правдой, поэтому гипотеза неверна и 2 ²ⁿ ! = O (2 ⁿ )