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

Part 1 : Yes

Note that, \(2^{n + 1} = 2 \cdot 2^n\)

So, for \(n \ge 1\) and any \(c \ge 2\), \(0 \le 2^{n + 1} \le c \cdot 2^n\).

Therefore, \(2^{n + 1} = O(2^n)\).

Part 2 : No

Note that, \(2^{2n} = 2^n \cdot 2^n\)

Now, for \(2^{2n}\) to be \(O(2^n)\), we’ll need a constant \(c\), such that \(0 \le 2^n \cdot 2^n \le c \cdot 2^n\).

It is evident that we’ll need \(c \ge 2^n\). But this is not possible for any arbitrarily large value of \(n\). No matter what value of \(c\) we choose, for some larger value \(n\), it will not be sufficient.

So, \(2^{2n}\) cannot be \(O(2^n)\).