3
$\begingroup$

I'm learning about Big-O notation for algorithm runtime, and I need some help understanding one part.

I read that for enter image description here the constant, c, does not matter as the function increases rapidly.

Does that mean that enter image description here?

$\endgroup$
  • 3
    $\begingroup$ No, $3^n$ is not in $O(2^n)$... there is no positive constant $K$ such that $3^n \le K\cdot 2^n$ for sufficiently large $n$. Sometimes one speaks of $3^n$ being in $O^*(2^n)$; that is, $\log(3^n)$ is $O(\log 2^n)$. $\endgroup$ – mjqxxxx May 4 '15 at 5:13

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.