# Asymptotic Proofs - BigOh/BigTheta

This is not homework, but from a past exam. I do not know how to solve this one at all. Can anyone please take the time and show me how to do these? Thank you.

Prove that $5^n \in O(6^n)$, but that $5^n \notin \Theta(6^n)$. (Doing this shows that $6^n$ bounds $5^n$ from above, but that $6^n$ is not the tightest such bound.)

I am familiar with the definitions, but it seems that $5^n$ is clearly $\lt 6^n$. and $5^n$ is not $\gt 6^n$.

• Don't forget that asymptotic notation is only up to constants. Your first observation shows that $5^n = O(6^n)$, but your second observation is not enough, for example, $n$ is not $\geq 2n$ yet $n = \Theta(2n)$. – Yuval Filmus Sep 30 '14 at 20:26
• Don't just remove the actual question. Future users should be able to find this and also profit from the effort of the people answering. – FrankW Sep 30 '14 at 22:13
• Do not remove the content of your question. This is a site for questions and answers with lasting value, not a chatroom where questions are forgotten once they scroll off the screen. Answers are not just for you, but also for all future visitors. This is a formal moderator warning, further vandalism of your question may result in a loss of posting privileges. – Gilles 'SO- stop being evil' Oct 1 '14 at 6:59
• Our reference questions have all the answers for you. – Raphael Oct 1 '14 at 7:03

First we show that $5^n \in O(6^n)$. To do this, we need to find constants $n_0$ and $c$ such that, for all $n > n_0$, $5^n \leq c6^n$. Without getting into a deep philosophical discussion about how I arrived at these constants, you should be able to convince yourself that $n_0 = 1$ and $c = 1$ work.

Now, to show that $5^n \notin \Theta(6^n)$, we need to show that $5^n \notin \Omega(6^n)$. This is because we already know $5^n \in O(6^n)$ and $\Theta(6^n)$ is simply $O(6^n) \cap \Omega(6^n)$. Read that a few times to make sure we're on the same page. For simplicity's sake, we can stick with $O$ and show that $6^n \notin O(5^n)$, which is equivalent to our condition.

To show that $6^n \notin O(5^n)$, we need to show that for any $c$ we pick, there's an $n_0$ after which $6^n > c5^n$; in other words, no matter what constant we multiply $5^n$ by, $6^n$ always eventually wins. To do this, we can calculate $n_0$ from $c$. We solve:

$$6^n > c5^n$$ $$\frac{6^n}{5^n} > c$$ $$1.2^n > c$$ $$n > log_{1.2} c$$

We can choose the smallest integer greater than the RHS and get a value for $n_0$ that will break any $c$ we choose. For instance, for $c = 10^{100}$, my formula says that 1,263 should work for $n_0$. Plugging in, looks like we're good to go.

Hint: Show that $$\lim_{n\to\infty} \frac{5^n}{6^n} = 0.$$

• This shows that $5^n = o(6^n)$, and in particular $5^n \neq \Theta(6^n)$. – Yuval Filmus Sep 30 '14 at 22:23
• I don't understand why this answer is down-voted. – D.W. Sep 30 '14 at 23:01
• @D.W. I wager because this is a hint that is only comprehensible if you understand O well, not at the level where you need to ask the question. As an answer to this question, it's pretty useless. – Gilles 'SO- stop being evil' Oct 1 '14 at 7:00