1

I read that $3^n$ = $2^{O(n)}$. But shouldnt having a base 3 be exponentially larger than having a base 2 ?

Link L
  • 717

1 Answers1

4

Hint: $$ a^n = b^{\log_{b}(a^n)} = b^{(\log_b a) \cdot n} $$

Adriano
  • 41,576
  • Another way of looking at it is this: $2^n\leq 3^n\leq 2^{2n}\ (=4^n)$, so some number $x$ between $n$ and $2n$ gives $3^n=2^x$. The bounds $n\leq x\leq 2n$ ensure that $x=O(n)$. – Teddy38 Sep 19 '17 at 07:34