1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Sep 30 '14 at 20:26
  • 2
    $\begingroup$ 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. $\endgroup$ – FrankW Sep 30 '14 at 22:13
  • 2
    $\begingroup$ 1. ogtan2k4, please don't delete changes that others have made to your question to improve it, and don't delete the text of your question -- that violates site rules and is sometimes considered "vandalism". See, e.g., cs.stackexchange.com/help/editing. 2. As far as the question itself, this is a problem dump. We expect you to make a serious effort on your own, to show us what you have tried and where you got stuck, and to try to frame a more precise question. We want to help you with your conceptual problems, not just solve your exercise for you (that wouldn't help you or us). $\endgroup$ – D.W. Sep 30 '14 at 23:00
  • 2
    $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' Oct 1 '14 at 6:59
  • 1
    $\begingroup$ Our reference questions have all the answers for you. $\endgroup$ – Raphael Oct 1 '14 at 7:03
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This shows that $5^n = o(6^n)$, and in particular $5^n \neq \Theta(6^n)$. $\endgroup$ – Yuval Filmus Sep 30 '14 at 22:23
  • $\begingroup$ I don't understand why this answer is down-voted. $\endgroup$ – D.W. Sep 30 '14 at 23:01
  • $\begingroup$ @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. $\endgroup$ – Gilles 'SO- stop being evil' Oct 1 '14 at 7:00

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.