3
$\begingroup$

I have a homework assignment (though this isn't part of it!) which I want to be sure on. This may be a stupid question.

The functions in question are $f(n) = 2^n$ and $g(n) = 3^n$. I'm pretty sure about the following:

$f$ is $O(g)$ as $2^n \leq 3^n \ \forall \ n \in \mathbb{N}$, using $c = 1$.

$f$ is also $\Omega(g)$. Proof:

$f$ being $\Omega(g)$ means that for some $c > 0$ we have that $c \cdot 2^n \geq 3^n$ for sufficiently large $n$.

Taking $log_3$ of both sides gives us $\log_3(c \cdot 2^n) \geq n$.

We can use change-of-base to get: $\frac{\log_2(c \cdot 2^n)}{\log_2(3)} \geq n$.

Log rules give us $\frac{\log_2(c)}{\log_2(3)} + \frac{n}{\log_2(3)} \geq n$.

This shows that $f$ is $\Omega(g)$ if $n$ is $\Omega(n)$, with some $c$ equal to $\frac{1}{log_2(3)}$.

If there are any problems, please let me know.

Thanks!

$\endgroup$
  • 2
    $\begingroup$ You don't switch the inequality sign when taking logs.... $\endgroup$ – mathworker21 Jan 10 '19 at 4:03
  • $\begingroup$ @mathworker21 you're right - changed $\endgroup$ – FibroMyAlgebra Jan 10 '19 at 4:05
  • $\begingroup$ Your last inequality implies this is only true for $n\le\frac{\log_2c}{\log_23-1}=k$, so whatever value of $c$ you chose, it will not be true for $n>k$ $\endgroup$ – Shubham Johri Jan 10 '19 at 4:09
  • $\begingroup$ @ShubhamJohri could you explain that further, please? $\endgroup$ – FibroMyAlgebra Jan 10 '19 at 4:11
  • $\begingroup$ @mathworker21 Thanks. Realized that that wasn't the main problem (and deleted the comment). But now that is the problem. $\endgroup$ – DirkGently Jan 10 '19 at 4:13
2
$\begingroup$

You have correctly (as far as I can see from a quick read) rewritten the condition to $$\frac{\log_2(c)}{\log_2(3)} + \frac{n}{\log_2(3)} \geq n$$ But then you need to argue that you can make this true for all sufficiently large $n$ just by choosing $c$ right -- and that is not the case.

The factor $\frac{1}{\log_2 3}$ is less than $1$, so the difference between the two terms involving $n$ gets ever larger the larger $n$ is. Therefore, no matter what you take $c$ to be, this difference will eventually be more than the constant $\frac{\log_2c}{\log_23}$, and therefore your rewritten inequality does not hold for all large enough $n$ -- also no matter what you take "large enough" to mean.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There we go. Thanks! I really appreciate the help. I'm pretty new to the wonderful world of asymptotics. $\endgroup$ – FibroMyAlgebra Jan 10 '19 at 4:15
1
$\begingroup$

Simpler approach: $$\frac{c 2^n}{3^n} \to 0$$ no matter what $c$ is, so $2^n$ is not $\Omega(3^n)$.


Using your approach: Because $\log_2(3) > 1$ we will always have $\frac{\log_2(c)}{\log_2(3)} + \frac{n}{\log_2(3)} \le n$ for all sufficiently large $n$, no matter what $c$ is.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ he's probably asking what the flaw in his logic is $\endgroup$ – mathworker21 Jan 10 '19 at 4:04
  • $\begingroup$ Yes. Could you explain further? $\endgroup$ – FibroMyAlgebra Jan 10 '19 at 4:05
  • $\begingroup$ @angryavian Sorry, did I mess up my ineq signs or did you mess up yours? I think you mean $\geq$ there as $f = Ω(g)$ means: $\exists c > 0$, $n_0 \geq 0$ such that $g(n) \leq cf(n)$ for all $n \geq n_0$. $\endgroup$ – FibroMyAlgebra Jan 10 '19 at 4:10
  • $\begingroup$ @FibroMyAlgebra From your work, you showed that you want to find a $c$ such that $\frac{\log_2(c)}{\log_2(3)} + \frac{n}{\log_2(3)} \ge n$ for all large $n$. In my answer I note that this is impossible, since the left-hand side is a line (as a function of $n$ with a smaller slope than the slope of the right-hand side. $\endgroup$ – angryavian Jan 10 '19 at 4:14
  • $\begingroup$ Ah, I see. @henningmakholm also answered this. Thanks! $\endgroup$ – FibroMyAlgebra Jan 10 '19 at 4:15

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.