I would like to show that $2^{2n} \notin O(2^n)$. I would like to avoid using limits. My current approach is the following:

$$2^{2n} = 4^n \leq c \cdot 2^n \implies 2^n \leq c$$

Which is not possible, hence it is $2^{2n} \notin O(2^n)$. Is this valid?

  • 3
    $\begingroup$ Yes, it is valid. $\endgroup$
    – coffeemath
    Sep 14 '20 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.