Mixing
Big O or Omega?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
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) = dfracn^3log(n), f_2(n)=n^9+2.2^n text and g_1(n)=(n+1)^3, g_2(n)=2^n+2^fracn2$
Decide whether the different combinations are $f_i=O(g_j(n)) textand/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$
real-analysis asymptotics
edited 1 hour ago
Alex Francisco
17k92149
asked 2 hours ago
ʎpoqou
1701110
add a comment |Â
up vote
3
down vote
favorite
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) = dfracn^3log(n), f_2(n)=n^9+2.2^n text and g_1(n)=(n+1)^3, g_2(n)=2^n+2^fracn2$
Decide whether the different combinations are $f_i=O(g_j(n)) textand/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$
real-analysis asymptotics
edited 1 hour ago
Alex Francisco
17k92149
asked 2 hours ago
ʎpoqou
1701110
1
I assume you already know that $2^frac n2$ is unimportant here since it equals $sqrt2^n$ and so is asymptotically insignificant compared to the term $2^n$.
– String
38 mins ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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) = dfracn^3log(n), f_2(n)=n^9+2.2^n text and g_1(n)=(n+1)^3, g_2(n)=2^n+2^fracn2$
Decide whether the different combinations are $f_i=O(g_j(n)) textand/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$
real-analysis asymptotics
edited 1 hour ago
Alex Francisco
17k92149
asked 2 hours ago
ʎpoqou
1701110
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) = dfracn^3log(n), f_2(n)=n^9+2.2^n text and g_1(n)=(n+1)^3, g_2(n)=2^n+2^fracn2$
Decide whether the different combinations are $f_i=O(g_j(n)) textand/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$
real-analysis asymptotics
real-analysis asymptotics
edited 1 hour ago
Alex Francisco
17k92149
asked 2 hours ago
ʎpoqou
1701110
edited 1 hour ago
Alex Francisco
17k92149
asked 2 hours ago
ʎpoqou
1701110
edited 1 hour ago
Alex Francisco
17k92149
edited 1 hour ago
Alex Francisco
17k92149
edited 1 hour ago
Alex Francisco
17k92149
17k92149
asked 2 hours ago
ʎpoqou
1701110
asked 2 hours ago
ʎpoqou
1701110
asked 2 hours ago
ʎpoqou
1701110
1701110
1
I assume you already know that $2^frac n2$ is unimportant here since it equals $sqrt2^n$ and so is asymptotically insignificant compared to the term $2^n$.
– String
38 mins ago
add a comment |Â
1
I assume you already know that $2^frac n2$ is unimportant here since it equals $sqrt2^n$ and so is asymptotically insignificant compared to the term $2^n$.
– String
38 mins ago
1
1
I assume you already know that $2^frac n2$ is unimportant here since it equals $sqrt2^n$ and so is asymptotically insignificant compared to the term $2^n$.
– String
38 mins ago
I assume you already know that $2^frac n2$ is unimportant here since it equals $sqrt2^n$ and so is asymptotically insignificant compared to the term $2^n$.
– String
38 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
You can represent it by $e$ and $log2$, $log(2.2)$:
$dfracf_2(n)g_2(n)= dfracn^9+(2.2)^n2^n+2^fracn2 geq dfrac(2.2)^n2^n+2^fracn2geq dfrac(2.2)^n2cdot 2^n =frac12e^n(log2.2-log2)$
And similarly:
$dfracf_2(n)g_2(n)leq 2e^n(log2.2-log2)$
answered 53 mins ago
Keen-ameteur
886214
Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $Omega$
– ÊŽpoqou
4 mins ago
add a comment |Â
up vote
2
down vote
Suppose we have $a>b>1$. Then
$$
fraca^nb^n=left(fracabright)^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.
answered 42 mins ago
String
13.4k32754
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
You can represent it by $e$ and $log2$, $log(2.2)$:
$dfracf_2(n)g_2(n)= dfracn^9+(2.2)^n2^n+2^fracn2 geq dfrac(2.2)^n2^n+2^fracn2geq dfrac(2.2)^n2cdot 2^n =frac12e^n(log2.2-log2)$
And similarly:
$dfracf_2(n)g_2(n)leq 2e^n(log2.2-log2)$
answered 53 mins ago
Keen-ameteur
886214
Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $Omega$
– ÊŽpoqou
4 mins ago
add a comment |Â
up vote
3
down vote
accepted
You can represent it by $e$ and $log2$, $log(2.2)$:
$dfracf_2(n)g_2(n)= dfracn^9+(2.2)^n2^n+2^fracn2 geq dfrac(2.2)^n2^n+2^fracn2geq dfrac(2.2)^n2cdot 2^n =frac12e^n(log2.2-log2)$
And similarly:
$dfracf_2(n)g_2(n)leq 2e^n(log2.2-log2)$
answered 53 mins ago
Keen-ameteur
886214
Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $Omega$
– ÊŽpoqou
4 mins ago
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
You can represent it by $e$ and $log2$, $log(2.2)$:
$dfracf_2(n)g_2(n)= dfracn^9+(2.2)^n2^n+2^fracn2 geq dfrac(2.2)^n2^n+2^fracn2geq dfrac(2.2)^n2cdot 2^n =frac12e^n(log2.2-log2)$
And similarly:
$dfracf_2(n)g_2(n)leq 2e^n(log2.2-log2)$
answered 53 mins ago
Keen-ameteur
886214
You can represent it by $e$ and $log2$, $log(2.2)$:
$dfracf_2(n)g_2(n)= dfracn^9+(2.2)^n2^n+2^fracn2 geq dfrac(2.2)^n2^n+2^fracn2geq dfrac(2.2)^n2cdot 2^n =frac12e^n(log2.2-log2)$
And similarly:
$dfracf_2(n)g_2(n)leq 2e^n(log2.2-log2)$
answered 53 mins ago
Keen-ameteur
886214
answered 53 mins ago
Keen-ameteur
886214
answered 53 mins ago
Keen-ameteur
886214
answered 53 mins ago
Keen-ameteur
886214
886214
Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $Omega$
– ÊŽpoqou
4 mins ago
add a comment |Â
Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $Omega$
– ÊŽpoqou
4 mins ago
Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $Omega$
– ÊŽpoqou
4 mins ago
Is it okay that the upper/lower bound depends on $n$? Perhaps I did not fully understand the notion of $O$ and $Omega$
– ÊŽpoqou
4 mins ago
add a comment |Â
up vote
2
down vote
Suppose we have $a>b>1$. Then
$$
fraca^nb^n=left(fracabright)^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.
answered 42 mins ago
String
13.4k32754
add a comment |Â
up vote
2
down vote
Suppose we have $a>b>1$. Then
$$
fraca^nb^n=left(fracabright)^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.
answered 42 mins ago
String
13.4k32754
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Suppose we have $a>b>1$. Then
$$
fraca^nb^n=left(fracabright)^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.
answered 42 mins ago
String
13.4k32754
Suppose we have $a>b>1$. Then
$$
fraca^nb^n=left(fracabright)^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.
answered 42 mins ago
String
13.4k32754
answered 42 mins ago
String
13.4k32754
answered 42 mins ago
String
13.4k32754
answered 42 mins ago
String
13.4k32754
13.4k32754
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2946850%2fbig-o-or-omega%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
I assume you already know that $2^frac n2$ is unimportant here since it equals $sqrt2^n$ and so is asymptotically insignificant compared to the term $2^n$.
– String
38 mins ago