53 views
Is $2^{n+1} = O(2^n)$? $2^{2n} = O(2^n)$$?$
| 53 views

> Is $2^{n+1} = O(2^{n})$ ?

Yes.

- Reason : $\space 2 \cdot 2^{n} \le c \cdot 2^{n}$ where $c$ is a positive real number, $c \ge 2$ in this particular case.

> Is $2^{2n} = O(2^{n})$ ?

- No.

- Reason :

$2^{n+n} \le c \cdot 2^{n}$ where c is a positive real number. There's no such constant $c$ that satisfies this inequality.

by Active (1.6k points)
selected
+1
In first case,  $c \geq 2$, So, we can find atleast one positive real 'c' for which definition of Big O will be satisfied.. Right?
0
Yes.
0
bro, you have written "c=2 in this particular case". it can be 3,4,5,...
+1

Yes. You're right. It can be 3, 4, 5... etc. I stopped after 2 since we need only one. I'll edit the answer anyways. Thank you for pointing it out :p