True or false: $2^{n+1} \in O(2^n)$, $2^{2n} \in O(2^n)$?

Question

Prove true or false:

$2^{n+1} \in O(2^n)$

$2^{2n} \in O(2^n)$

I don't know where to start, so any push or solution is appreciated.

I know constants doesn't matter in asymptotic complexity, so $n+50 \in O(n)$ right? But also$n^3 \notin O(n^2)$ because of bigger power, right?

But how does it work for $c^x $ and $c^{x+1}$ where $c$ is a constant?

And how to do a proper proof of this?

Thank you

Answer 1

Let us first give a rigorous definition of the big $ O $-notation.

Definition Let $ A \subseteq \mathbb{R} $ be unbounded from above, and suppose that $ f,g: A \to \mathbb{R} $. We then say that $ f(x) = O(g(x)) $ if and only if there exists a constant $ M > 0 $ such that $ |f(x)| \leq M |g(x)| $ for all $ x \in A $ sufficiently large.

Consider the functions $ f,g: \mathbb{N} \to \mathbb{R} $ defined by $$ \forall n \in \mathbb{N}: \quad f(n) := 2^{n + 1} \quad \text{and} \quad g(n) := 2^{n}. $$ As $ 2^{n + 1} = 2 \cdot 2^{n} $ for all $ n \in \mathbb{N} $, we see that $$ \forall n \in \mathbb{N}: \quad |f(n)| \leq 2 |g(n)|. $$ It thus follows from definition that $ f(n) = O(g(n)) $, which we can also write as $ 2^{n + 1} = O(2^{n}) $.

The second statement is seen to be false by the definition. This is because $$ \lim_{n \to \infty} \frac{2^{2n}}{2^{n}} = \lim_{n \to \infty} 2^{n} = \infty, $$ which means that we cannot find any $ M > 0 $ satisfying $ 2^{2n} \leq M \cdot 2^{n} $ for all $ n \in \mathbb{N} $ sufficiently large.

We have $ n + 50 = O(n) $ because the inequality $ n + 50 \leq 2n $ is satisfied for all $ n \in \mathbb{N}_{\geq 50} $. We have $ n^{3} \neq O(n^{2}) $ because $ \displaystyle \lim_{n \to \infty} \frac{n^{3}}{n^{2}} = \lim_{n \to \infty} n = \infty $.