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$
10
  • 2
    $\begingroup$ You don't switch the inequality sign when taking logs.... $\endgroup$ Jan 10, 2019 at 4:03
  • $\begingroup$ @mathworker21 you're right - changed $\endgroup$ Jan 10, 2019 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$ Jan 10, 2019 at 4:09
  • $\begingroup$ @ShubhamJohri could you explain that further, please? $\endgroup$ Jan 10, 2019 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, 2019 at 4:13

2 Answers 2

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.

$\endgroup$
1
  • $\begingroup$ There we go. Thanks! I really appreciate the help. I'm pretty new to the wonderful world of asymptotics. $\endgroup$ Jan 10, 2019 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.

$\endgroup$
5
  • $\begingroup$ he's probably asking what the flaw in his logic is $\endgroup$ Jan 10, 2019 at 4:04
  • $\begingroup$ Yes. Could you explain further? $\endgroup$ Jan 10, 2019 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$ Jan 10, 2019 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, 2019 at 4:14
  • $\begingroup$ Ah, I see. @henningmakholm also answered this. Thanks! $\endgroup$ Jan 10, 2019 at 4:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .