Mixing
How to prove that $n^{n-2} = O(2^{n^2})$ [closed]
$begingroup$
I'm struggling to show that : $n^{n-2} = O(2^{n^2})$
.
I know the definition of big O but I don't know any method to show this. Could you please help me giving a few methods?
computational-complexity
asked Jan 21 at 13:22
Marine GalantinMarine Galantin
862316
$endgroup$
closed as off-topic by mrtaurho, Abcd, Lord_Farin, Paul Frost, Eevee Trainer Jan 21 at 21:51
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – mrtaurho, Abcd, Lord_Farin, Paul Frost, Eevee Trainer
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
I'm struggling to show that : $n^{n-2} = O(2^{n^2})$
.
I know the definition of big O but I don't know any method to show this. Could you please help me giving a few methods?
computational-complexity
asked Jan 21 at 13:22
Marine GalantinMarine Galantin
862316
$endgroup$
closed as off-topic by mrtaurho, Abcd, Lord_Farin, Paul Frost, Eevee Trainer Jan 21 at 21:51
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – mrtaurho, Abcd, Lord_Farin, Paul Frost, Eevee Trainer
If this question can be reworded to fit the rules in the help center, please edit the question.
3
$begingroup$
$n^{n-2} = o(n^n)$, and $n^n leq (2^n)^n=2^{n^2}$.
$endgroup$
– Mindlack
Jan 21 at 13:24
1
$begingroup$
The takeaway from this is that exponents matter much more than bases. The same approach shows $n^n=o(2^{n^2})$. Even though the base of $n^n$ is rising it can't compete with the larger exponent.
$endgroup$
– Ross Millikan
Jan 21 at 18:30
add a comment |
$begingroup$
I'm struggling to show that : $n^{n-2} = O(2^{n^2})$
.
I know the definition of big O but I don't know any method to show this. Could you please help me giving a few methods?
computational-complexity
asked Jan 21 at 13:22
Marine GalantinMarine Galantin
862316
$endgroup$
I'm struggling to show that : $n^{n-2} = O(2^{n^2})$
.
I know the definition of big O but I don't know any method to show this. Could you please help me giving a few methods?
computational-complexity
computational-complexity
asked Jan 21 at 13:22
Marine GalantinMarine Galantin
862316
asked Jan 21 at 13:22
Marine GalantinMarine Galantin
862316
asked Jan 21 at 13:22
Marine GalantinMarine Galantin
862316
asked Jan 21 at 13:22
Marine GalantinMarine Galantin
862316
asked Jan 21 at 13:22
Marine GalantinMarine Galantin
862316
862316
closed as off-topic by mrtaurho, Abcd, Lord_Farin, Paul Frost, Eevee Trainer Jan 21 at 21:51
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – mrtaurho, Abcd, Lord_Farin, Paul Frost, Eevee Trainer
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by mrtaurho, Abcd, Lord_Farin, Paul Frost, Eevee Trainer Jan 21 at 21:51
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – mrtaurho, Abcd, Lord_Farin, Paul Frost, Eevee Trainer
If this question can be reworded to fit the rules in the help center, please edit the question.
3
$begingroup$
$n^{n-2} = o(n^n)$, and $n^n leq (2^n)^n=2^{n^2}$.
$endgroup$
– Mindlack
Jan 21 at 13:24
1
$begingroup$
The takeaway from this is that exponents matter much more than bases. The same approach shows $n^n=o(2^{n^2})$. Even though the base of $n^n$ is rising it can't compete with the larger exponent.
$endgroup$
– Ross Millikan
Jan 21 at 18:30
add a comment |
3
$begingroup$
$n^{n-2} = o(n^n)$, and $n^n leq (2^n)^n=2^{n^2}$.
$endgroup$
– Mindlack
Jan 21 at 13:24
1
$begingroup$
The takeaway from this is that exponents matter much more than bases. The same approach shows $n^n=o(2^{n^2})$. Even though the base of $n^n$ is rising it can't compete with the larger exponent.
$endgroup$
– Ross Millikan
Jan 21 at 18:30
3
3
$begingroup$
$n^{n-2} = o(n^n)$, and $n^n leq (2^n)^n=2^{n^2}$.
$endgroup$
– Mindlack
Jan 21 at 13:24
$begingroup$
$n^{n-2} = o(n^n)$, and $n^n leq (2^n)^n=2^{n^2}$.
$endgroup$
– Mindlack
Jan 21 at 13:24
1
1
$begingroup$
The takeaway from this is that exponents matter much more than bases. The same approach shows $n^n=o(2^{n^2})$. Even though the base of $n^n$ is rising it can't compete with the larger exponent.
$endgroup$
– Ross Millikan
Jan 21 at 18:30
$begingroup$
The takeaway from this is that exponents matter much more than bases. The same approach shows $n^n=o(2^{n^2})$. Even though the base of $n^n$ is rising it can't compete with the larger exponent.
$endgroup$
– Ross Millikan
Jan 21 at 18:30
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here is a less obvious approach for the cases when it will not be as simple as in Shubham's answer. Note that $f(x) < g(x) iff ln f(x) < ln g(x)$ and compare the logs to get
$$
lnleft(n^{n-2}right) = (n-2) ln n = Theta(n ln n)
$$
versus
$$
ln left(2^{n^2}right) = n^2 ln 2 = Thetaleft(n^2right)...
$$
answered Jan 21 at 13:29
gt6989bgt6989b
34.7k22456
$endgroup$
add a comment |
$begingroup$
$$lim_{ntoinfty}frac{n^{n-2}}{2^{n^2}}=lim_{ntoinfty}frac1{n^2}cdotBig(frac{n}{2^n}Big)^n=0$$
answered Jan 21 at 13:26
Shubham JohriShubham Johri
5,204718
$endgroup$
$begingroup$
so you proved that this is a little o, not a big o?
$endgroup$
– Marine Galantin
Jan 21 at 16:50
1
$begingroup$
@MarineGalantin $o implies O$
$endgroup$
– gt6989b
Jan 21 at 18:06
$begingroup$
yes that's why I asked :) I didn't thought about doing that why
$endgroup$
– Marine Galantin
Jan 21 at 18:07
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is a less obvious approach for the cases when it will not be as simple as in Shubham's answer. Note that $f(x) < g(x) iff ln f(x) < ln g(x)$ and compare the logs to get
$$
lnleft(n^{n-2}right) = (n-2) ln n = Theta(n ln n)
$$
versus
$$
ln left(2^{n^2}right) = n^2 ln 2 = Thetaleft(n^2right)...
$$
answered Jan 21 at 13:29
gt6989bgt6989b
34.7k22456
$endgroup$
add a comment |
$begingroup$
Here is a less obvious approach for the cases when it will not be as simple as in Shubham's answer. Note that $f(x) < g(x) iff ln f(x) < ln g(x)$ and compare the logs to get
$$
lnleft(n^{n-2}right) = (n-2) ln n = Theta(n ln n)
$$
versus
$$
ln left(2^{n^2}right) = n^2 ln 2 = Thetaleft(n^2right)...
$$
answered Jan 21 at 13:29
gt6989bgt6989b
34.7k22456
$endgroup$
add a comment |
$begingroup$
Here is a less obvious approach for the cases when it will not be as simple as in Shubham's answer. Note that $f(x) < g(x) iff ln f(x) < ln g(x)$ and compare the logs to get
$$
lnleft(n^{n-2}right) = (n-2) ln n = Theta(n ln n)
$$
versus
$$
ln left(2^{n^2}right) = n^2 ln 2 = Thetaleft(n^2right)...
$$
answered Jan 21 at 13:29
gt6989bgt6989b
34.7k22456
$endgroup$
Here is a less obvious approach for the cases when it will not be as simple as in Shubham's answer. Note that $f(x) < g(x) iff ln f(x) < ln g(x)$ and compare the logs to get
$$
lnleft(n^{n-2}right) = (n-2) ln n = Theta(n ln n)
$$
versus
$$
ln left(2^{n^2}right) = n^2 ln 2 = Thetaleft(n^2right)...
$$
answered Jan 21 at 13:29
gt6989bgt6989b
34.7k22456
edited Jan 21 at 18:06
answered Jan 21 at 13:29
gt6989bgt6989b
34.7k22456
answered Jan 21 at 13:29
gt6989bgt6989b
34.7k22456
answered Jan 21 at 13:29
gt6989bgt6989b
34.7k22456
34.7k22456
add a comment |
add a comment |
$begingroup$
$$lim_{ntoinfty}frac{n^{n-2}}{2^{n^2}}=lim_{ntoinfty}frac1{n^2}cdotBig(frac{n}{2^n}Big)^n=0$$
answered Jan 21 at 13:26
Shubham JohriShubham Johri
5,204718
$endgroup$
$begingroup$
so you proved that this is a little o, not a big o?
$endgroup$
– Marine Galantin
Jan 21 at 16:50
1
$begingroup$
@MarineGalantin $o implies O$
$endgroup$
– gt6989b
Jan 21 at 18:06
$begingroup$
yes that's why I asked :) I didn't thought about doing that why
$endgroup$
– Marine Galantin
Jan 21 at 18:07
add a comment |
$begingroup$
$$lim_{ntoinfty}frac{n^{n-2}}{2^{n^2}}=lim_{ntoinfty}frac1{n^2}cdotBig(frac{n}{2^n}Big)^n=0$$
answered Jan 21 at 13:26
Shubham JohriShubham Johri
5,204718
$endgroup$
$begingroup$
so you proved that this is a little o, not a big o?
$endgroup$
– Marine Galantin
Jan 21 at 16:50
1
$begingroup$
@MarineGalantin $o implies O$
$endgroup$
– gt6989b
Jan 21 at 18:06
$begingroup$
yes that's why I asked :) I didn't thought about doing that why
$endgroup$
– Marine Galantin
Jan 21 at 18:07
add a comment |
$begingroup$
$$lim_{ntoinfty}frac{n^{n-2}}{2^{n^2}}=lim_{ntoinfty}frac1{n^2}cdotBig(frac{n}{2^n}Big)^n=0$$
answered Jan 21 at 13:26
Shubham JohriShubham Johri
5,204718
$endgroup$
$$lim_{ntoinfty}frac{n^{n-2}}{2^{n^2}}=lim_{ntoinfty}frac1{n^2}cdotBig(frac{n}{2^n}Big)^n=0$$
answered Jan 21 at 13:26
Shubham JohriShubham Johri
5,204718
answered Jan 21 at 13:26
Shubham JohriShubham Johri
5,204718
answered Jan 21 at 13:26
Shubham JohriShubham Johri
5,204718
answered Jan 21 at 13:26
Shubham JohriShubham Johri
5,204718
5,204718
$begingroup$
so you proved that this is a little o, not a big o?
$endgroup$
– Marine Galantin
Jan 21 at 16:50
1
$begingroup$
@MarineGalantin $o implies O$
$endgroup$
– gt6989b
Jan 21 at 18:06
$begingroup$
yes that's why I asked :) I didn't thought about doing that why
$endgroup$
– Marine Galantin
Jan 21 at 18:07
add a comment |
$begingroup$
so you proved that this is a little o, not a big o?
$endgroup$
– Marine Galantin
Jan 21 at 16:50
1
$begingroup$
@MarineGalantin $o implies O$
$endgroup$
– gt6989b
Jan 21 at 18:06
$begingroup$
yes that's why I asked :) I didn't thought about doing that why
$endgroup$
– Marine Galantin
Jan 21 at 18:07
$begingroup$
so you proved that this is a little o, not a big o?
$endgroup$
– Marine Galantin
Jan 21 at 16:50
$begingroup$
so you proved that this is a little o, not a big o?
$endgroup$
– Marine Galantin
Jan 21 at 16:50
1
1
$begingroup$
@MarineGalantin $o implies O$
$endgroup$
– gt6989b
Jan 21 at 18:06
$begingroup$
@MarineGalantin $o implies O$
$endgroup$
– gt6989b
Jan 21 at 18:06
$begingroup$
yes that's why I asked :) I didn't thought about doing that why
$endgroup$
– Marine Galantin
Jan 21 at 18:07
$begingroup$
yes that's why I asked :) I didn't thought about doing that why
$endgroup$
– Marine Galantin
Jan 21 at 18:07
add a comment |
3
$begingroup$
$n^{n-2} = o(n^n)$, and $n^n leq (2^n)^n=2^{n^2}$.
$endgroup$
– Mindlack
Jan 21 at 13:24
1
$begingroup$
The takeaway from this is that exponents matter much more than bases. The same approach shows $n^n=o(2^{n^2})$. Even though the base of $n^n$ is rising it can't compete with the larger exponent.
$endgroup$
– Ross Millikan
Jan 21 at 18:30