I have to show that $3^x$ is $O(3^x - 2^x)$. I'm just starting to learn the basics of Big-Oh notation. I'm thinking you have to take logarithms here, but am stuck on how to show this is true once I get $log(3^x-2^x)$ (although it makes intuitive sense to me that this is true). Would appreciate any help!

  • 1
    $\begingroup$ Please see math.meta.stackexchange.com/questions/5020 $\endgroup$ – Lord Shark the Unknown Nov 1 '18 at 7:01
  • $\begingroup$ Consider $$\frac{3^x}{3^x-2^x}.$$ $\endgroup$ – Lord Shark the Unknown Nov 1 '18 at 7:01
  • $\begingroup$ What is that limit? $\endgroup$ – Lord Shark the Unknown Nov 1 '18 at 7:05
  • $\begingroup$ How would I compute that limit? Taking the log of the numerator and denominator, I get $xlog(3)$ in the numerator but don't know what to do with $log(3^x-2^x)$ in the denominator. $\endgroup$ – bob Nov 1 '18 at 7:06
  • $\begingroup$ @bob You don't have to find the limit (there doesn't even have to be a limit for big-$O$ to make sense). You just have to show that that that fraction is (for large enough $x$) bounded both below and above by positive numbers. $\endgroup$ – Arthur Nov 1 '18 at 7:07

Consider the fraction $\frac{3^x}{3^x-2^x}$. Clearly, for $x>0$, this fraction is larger than $1$ (the numerator is larger than the denominator), so it is bounded below. Not that this is actually necessary for $3^x=O(3^x-2^x)$.

For bounded above, which is necessary, consider $x>1$. Note that $2^x<2\cdot 3^{x-1}$. This gives $$ \frac{3^x}{3^x-2^x}<\frac{3^x}{3^x-2\cdot 3^{x-1}}=\frac3{3-2} $$ So the fraction is bounded above, and we're done.

  • $\begingroup$ This is perfect, thank you for clarifying! $\endgroup$ – bob Nov 1 '18 at 7:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.