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

Question

Is 2^(n+1) = O(2^n)?

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

---

2^(2n) = O(2^n)?

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

Answer 1

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

2n+1 = 2(2n)

и

22n = (2n)2

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

Answer 2

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

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

И то же самое относится к другому примеру: существует ли постоянная C такая, что 2^(2n) <= C(2^n) для всех 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

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

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

что явно неправильно, потому что нет такой постоянной, удовлетворяющих такое неравенство.

Answer 5

претензии: 2^(2n) = O (2^п)

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

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

Поэтому 2^(2n)! = O (2^п)