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

Question

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!

Answer 1

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.

Answer 2

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.