# Big O or Omega?

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$$

• I assume you already know that $2^{\frac n2}$ is unimportant here since it equals $\sqrt{2^n}$ and so is asymptotically insignificant compared to the term $2^n$. – String Oct 8 '18 at 10:14

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

• Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $\Omega$ – ʎpoqou Oct 8 '18 at 10:48
• @ʎpoqou: In what way do you mean depends on $n$? The definition of $f=O(g)$ says that for $n$ large enough, say larger than some $n_0$, the relation $f(n)\leq M g(n)$ holds independently of the specific choice of $n$ at that point. – String Oct 8 '18 at 11:00
• The last inequality appears to be wrong. Did you mean $$\frac{g_2(n)}{f_2(n)}\leq 2\operatorname{e}^{-n(\log 2.2-\log 2)}$$ – String Oct 8 '18 at 11:04
• I've added by edit where I think the last inequality stems from. And obviously the inequalities are true only from some point onwards. – Keen-ameteur Oct 8 '18 at 11:17
• @Keen-ameteur: Ah, sure! I see it now. Essentially you have established that $f_2$ over $g_2$ is Big Theta of some exponential expression which does make sense! Sorry for misunderstanding that! – String Oct 8 '18 at 11:35

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.