Cormen Edition 3 Exercise 3.1 Question 4 (Page No. 53)

Question

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

Answer 1

> 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.

 

Comments

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?

---

Yes.

---

bro, you have written "c=2 in this particular case". it can be 3,4,5,...

---

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