3
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – String Oct 8 '18 at 10:14
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $\Omega$ $\endgroup$ – ʎpoqou Oct 8 '18 at 10:48
  • 1
    $\begingroup$ @ʎ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. $\endgroup$ – String Oct 8 '18 at 11:00
  • 1
    $\begingroup$ 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)}$$ $\endgroup$ – String Oct 8 '18 at 11:04
  • 1
    $\begingroup$ I've added by edit where I think the last inequality stems from. And obviously the inequalities are true only from some point onwards. $\endgroup$ – Keen-ameteur Oct 8 '18 at 11:17
  • 1
    $\begingroup$ @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! $\endgroup$ – String Oct 8 '18 at 11:35
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.