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$
Best Answer
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)}$