# Is n O(n)? Is n Ω(n)?

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!

• You don't switch the inequality sign when taking logs.... – mathworker21 Jan 10 '19 at 4:03
• @mathworker21 you're right - changed – FibroMyAlgebra Jan 10 '19 at 4:05
• 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$ – Shubham Johri Jan 10 '19 at 4:09
• @ShubhamJohri could you explain that further, please? – FibroMyAlgebra Jan 10 '19 at 4:11
• @mathworker21 Thanks. Realized that that wasn't the main problem (and deleted the comment). But now that is the problem. – DirkGently Jan 10 '19 at 4:13

## 2 Answers

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.

• There we go. Thanks! I really appreciate the help. I'm pretty new to the wonderful world of asymptotics. – FibroMyAlgebra Jan 10 '19 at 4:15

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.

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