Big O or Omega?

Question

Good day,

I am going over a problem sheet right now and I can not seem to figure out the last combination of functions and their bounds.

We are given,

$f_1(n) = \dfrac{n^3}{log(n)}, \ f_2(n)=n^9+2.2^n \text{ and } g_1(n)=(n+1)^3, \ g_2(n)=2^n+2^{\frac{n}{2}}$

Decide whether the different combinations are $f_i=O(g_j(n)) \ \text{and/or} \ f_i=\Omega(g_j(n)).$

What I got so far is that $f_1=O(g_1),\ f_1=O(g_2), \ f_2=\Omega(g_1)$

I am stuck on the combination $f_2, \ g_2$.

I am not sure what I can do to show that it works because of $2.2^n$

Answer 1

You can represent it by $e$ and $\log2$, $\log(2.2)$:

$\dfrac{f_2(n)}{g_2(n)}= \dfrac{n^9+(2.2)^n}{2^n+2^{\frac{n}{2}}} \geq \dfrac{(2.2)^n}{2^n+2^{\frac{n}{2}}}\geq \dfrac{(2.2)^n}{2\cdot 2^n} =\frac{1}{2}e^{n(\log2.2-\log2)}$

And similarly:

$\dfrac{f_2(n)}{g_2(n)}= \dfrac{n^9+(2.2)^n}{2^n+2^{\frac{n}{2}}} \leq \dfrac{2\cdot(2.2)^n}{2^n}\leq 2e^{n(\log2.2-\log2)}$

Answer 2

Suppose we have $a>b>1$. Then $$ \frac{a^n}{b^n}=\left(\frac{a}{b}\right)^n=(1+r)^n $$ for some $r>0$ and this grows exponentially as $n$ tends to infinity. Thus $a^n$ wins out asymptotically although $b^n$ also tends to infinity.