Determine whether each pair is $f(n) = O(g(n), f(n) = \Omega(g(n)), or f(n) = \Theta(g(n)).$

Question

For the pair of functions, find whether it's $f(n) = O(g(n), f(n) = \Omega(g(n)), or f(n) = \Theta(g(n)):$

$a) f(n) = 12^n , g(n) = 7^n$

$b) f(n) = log_9(n^4), g(n) = log_9(n^5)$

I understand that:

$f(n)$ is $O(g(n))$ if $C$ and $n_0$, $f(n) \leq C * g(n)$ $\forall n>n_o$

$f(n)$ is $\Omega(g(n))$ if $C$ and $n_0$, $f(n) \geq C * g(n)$ $\forall n>n_o$

$f(n)$ is $\Theta g(n))$ iff $f(n)$ is $O(g(n))$ and $f(n)$ is $\Omega(g(n))$

but how do I determine which one is which? Am I inputting some value for n? By looking at some you can tell already what it is but how would I prove it? I saw some people using limits? Do I put $f(n)/g(n)$ and then figure it out that way?

Thanks in advance.

Answer 1

The first one is not too hard: $g(n) \leq f(n)$ for every $n$, so $f(n) = O(g(n))$. To prove that $g(n) \neq O(f(n))$, let $C>0$ be arbitrary. Find $n_0$ so that $(12/7)^{n_0} > C$ (how?). Then if $n \geq n_0$ then $12^n \geq C 7^n$.

For the second one, here's a hint: $\log_9(n^4)=4 \log_9(n)$, $\log_9(n^5)=5 \log_9(n)$.