Mixing
Why does n! have the least time?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I was reading the book Introduction to Algorithms, Chapter 1. When I saw this diagram, I got confused because $lg n$ has the largest value of time while $n!$ has the least value of time. And that doesn't make sense to me - perhaps I misunderstood this?
algorithms time-complexity
edited Aug 28 at 13:21
psmears
43935
asked Aug 27 at 7:54
Mohamed Magdy
2013
add a comment |Â
up vote
1
down vote
favorite
I was reading the book Introduction to Algorithms, Chapter 1. When I saw this diagram, I got confused because $lg n$ has the largest value of time while $n!$ has the least value of time. And that doesn't make sense to me - perhaps I misunderstood this?
algorithms time-complexity
edited Aug 28 at 13:21
psmears
43935
asked Aug 27 at 7:54
Mohamed Magdy
2013
15
This question is almost unclear, if the book mention was omitted. You never mentioned in the question what the numbers in the table is supposed to be.
– user92772
Aug 27 at 13:36
As shown by the comments under Josh Chen's answer, I'd say this question is very unclear. Please tell us what the book says about what the table represents.
– JiK
Aug 28 at 10:56
@JiK From the $n$ row, the tabulated values are the maximum $n$ such that $f(n)leq y$, where $f(n)$ is the function in the left column and $y$ is the number of milliseconds in the period of time stated at the top of hte column.
– David Richerby
Aug 28 at 12:53
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I was reading the book Introduction to Algorithms, Chapter 1. When I saw this diagram, I got confused because $lg n$ has the largest value of time while $n!$ has the least value of time. And that doesn't make sense to me - perhaps I misunderstood this?
algorithms time-complexity
edited Aug 28 at 13:21
psmears
43935
asked Aug 27 at 7:54
Mohamed Magdy
2013
I was reading the book Introduction to Algorithms, Chapter 1. When I saw this diagram, I got confused because $lg n$ has the largest value of time while $n!$ has the least value of time. And that doesn't make sense to me - perhaps I misunderstood this?
algorithms time-complexity
edited Aug 28 at 13:21
psmears
43935
asked Aug 27 at 7:54
Mohamed Magdy
2013
edited Aug 28 at 13:21
psmears
43935
edited Aug 28 at 13:21
psmears
43935
edited Aug 28 at 13:21
psmears
43935
43935
asked Aug 27 at 7:54
Mohamed Magdy
2013
asked Aug 27 at 7:54
Mohamed Magdy
2013
asked Aug 27 at 7:54
Mohamed Magdy
2013
2013
15
This question is almost unclear, if the book mention was omitted. You never mentioned in the question what the numbers in the table is supposed to be.
– user92772
Aug 27 at 13:36
As shown by the comments under Josh Chen's answer, I'd say this question is very unclear. Please tell us what the book says about what the table represents.
– JiK
Aug 28 at 10:56
@JiK From the $n$ row, the tabulated values are the maximum $n$ such that $f(n)leq y$, where $f(n)$ is the function in the left column and $y$ is the number of milliseconds in the period of time stated at the top of hte column.
– David Richerby
Aug 28 at 12:53
add a comment |Â
15
This question is almost unclear, if the book mention was omitted. You never mentioned in the question what the numbers in the table is supposed to be.
– user92772
Aug 27 at 13:36
As shown by the comments under Josh Chen's answer, I'd say this question is very unclear. Please tell us what the book says about what the table represents.
– JiK
Aug 28 at 10:56
@JiK From the $n$ row, the tabulated values are the maximum $n$ such that $f(n)leq y$, where $f(n)$ is the function in the left column and $y$ is the number of milliseconds in the period of time stated at the top of hte column.
– David Richerby
Aug 28 at 12:53
15
15
This question is almost unclear, if the book mention was omitted. You never mentioned in the question what the numbers in the table is supposed to be.
– user92772
Aug 27 at 13:36
This question is almost unclear, if the book mention was omitted. You never mentioned in the question what the numbers in the table is supposed to be.
– user92772
Aug 27 at 13:36
As shown by the comments under Josh Chen's answer, I'd say this question is very unclear. Please tell us what the book says about what the table represents.
– JiK
Aug 28 at 10:56
As shown by the comments under Josh Chen's answer, I'd say this question is very unclear. Please tell us what the book says about what the table represents.
– JiK
Aug 28 at 10:56
@JiK From the $n$ row, the tabulated values are the maximum $n$ such that $f(n)leq y$, where $f(n)$ is the function in the left column and $y$ is the number of milliseconds in the period of time stated at the top of hte column.
– David Richerby
Aug 28 at 12:53
@JiK From the $n$ row, the tabulated values are the maximum $n$ such that $f(n)leq y$, where $f(n)$ is the function in the left column and $y$ is the number of milliseconds in the period of time stated at the top of hte column.
– David Richerby
Aug 28 at 12:53
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
35
down vote
accepted
The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.
i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.
One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.
For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).
answered Aug 27 at 7:58
Josh Chen
44647
10
Yes, that's how the authors want us to read that table. It's mostly bogus, of course, since ignoring (potentially wildly different) constant factors makes the numbers meaningless. So we better ignore the specific numbers.
– Raphael♦
Aug 27 at 10:15
7
Yeah, the table is wrong actually. Yesterday, I ran an $O(n)$ algorithm for a month, and it didn't consume $2592cdot 10^9$ characters of input! In fact it only consumed $259198cdot 10^7$ characters.
– leftaroundabout
Aug 27 at 14:46
6
@Raphael Looks to me as if this is a table assuming you take f(n) microseconds, not just O (f(n)).
– gnasher729
Aug 27 at 15:25
6
@leftaroundabout Yesterday you ran an algorithm for a month? With a bit of work you should be ready for a Nobel prize.
– gnasher729
Aug 27 at 15:27
1
According to the table it would take an input of size $17$ to run an $O(n!)$ algorithm for a century, not ~$10$
– SamYonnou
Aug 27 at 16:16
 |Â
show 7 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
35
down vote
accepted
The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.
i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.
One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.
For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).
answered Aug 27 at 7:58
Josh Chen
44647
10
Yes, that's how the authors want us to read that table. It's mostly bogus, of course, since ignoring (potentially wildly different) constant factors makes the numbers meaningless. So we better ignore the specific numbers.
– Raphael♦
Aug 27 at 10:15
7
Yeah, the table is wrong actually. Yesterday, I ran an $O(n)$ algorithm for a month, and it didn't consume $2592cdot 10^9$ characters of input! In fact it only consumed $259198cdot 10^7$ characters.
– leftaroundabout
Aug 27 at 14:46
6
@Raphael Looks to me as if this is a table assuming you take f(n) microseconds, not just O (f(n)).
– gnasher729
Aug 27 at 15:25
6
@leftaroundabout Yesterday you ran an algorithm for a month? With a bit of work you should be ready for a Nobel prize.
– gnasher729
Aug 27 at 15:27
1
According to the table it would take an input of size $17$ to run an $O(n!)$ algorithm for a century, not ~$10$
– SamYonnou
Aug 27 at 16:16
 |Â
show 7 more comments
up vote
35
down vote
accepted
The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.
i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.
One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.
For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).
answered Aug 27 at 7:58
Josh Chen
44647
10
Yes, that's how the authors want us to read that table. It's mostly bogus, of course, since ignoring (potentially wildly different) constant factors makes the numbers meaningless. So we better ignore the specific numbers.
– Raphael♦
Aug 27 at 10:15
7
Yeah, the table is wrong actually. Yesterday, I ran an $O(n)$ algorithm for a month, and it didn't consume $2592cdot 10^9$ characters of input! In fact it only consumed $259198cdot 10^7$ characters.
– leftaroundabout
Aug 27 at 14:46
6
@Raphael Looks to me as if this is a table assuming you take f(n) microseconds, not just O (f(n)).
– gnasher729
Aug 27 at 15:25
6
@leftaroundabout Yesterday you ran an algorithm for a month? With a bit of work you should be ready for a Nobel prize.
– gnasher729
Aug 27 at 15:27
1
According to the table it would take an input of size $17$ to run an $O(n!)$ algorithm for a century, not ~$10$
– SamYonnou
Aug 27 at 16:16
 |Â
show 7 more comments
up vote
35
down vote
accepted
up vote
35
down vote
accepted
The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.
i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.
One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.
For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).
answered Aug 27 at 7:58
Josh Chen
44647
The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.
i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.
One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.
For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).
answered Aug 27 at 7:58
Josh Chen
44647
edited Aug 27 at 12:17
answered Aug 27 at 7:58
Josh Chen
44647
answered Aug 27 at 7:58
Josh Chen
44647
answered Aug 27 at 7:58
Josh Chen
44647
44647
10
Yes, that's how the authors want us to read that table. It's mostly bogus, of course, since ignoring (potentially wildly different) constant factors makes the numbers meaningless. So we better ignore the specific numbers.
– Raphael♦
Aug 27 at 10:15
7
Yeah, the table is wrong actually. Yesterday, I ran an $O(n)$ algorithm for a month, and it didn't consume $2592cdot 10^9$ characters of input! In fact it only consumed $259198cdot 10^7$ characters.
– leftaroundabout
Aug 27 at 14:46
6
@Raphael Looks to me as if this is a table assuming you take f(n) microseconds, not just O (f(n)).
– gnasher729
Aug 27 at 15:25
6
@leftaroundabout Yesterday you ran an algorithm for a month? With a bit of work you should be ready for a Nobel prize.
– gnasher729
Aug 27 at 15:27
1
According to the table it would take an input of size $17$ to run an $O(n!)$ algorithm for a century, not ~$10$
– SamYonnou
Aug 27 at 16:16
 |Â
show 7 more comments
10
Yes, that's how the authors want us to read that table. It's mostly bogus, of course, since ignoring (potentially wildly different) constant factors makes the numbers meaningless. So we better ignore the specific numbers.
– Raphael♦
Aug 27 at 10:15
7
Yeah, the table is wrong actually. Yesterday, I ran an $O(n)$ algorithm for a month, and it didn't consume $2592cdot 10^9$ characters of input! In fact it only consumed $259198cdot 10^7$ characters.
– leftaroundabout
Aug 27 at 14:46
6
@Raphael Looks to me as if this is a table assuming you take f(n) microseconds, not just O (f(n)).
– gnasher729
Aug 27 at 15:25
6
@leftaroundabout Yesterday you ran an algorithm for a month? With a bit of work you should be ready for a Nobel prize.
– gnasher729
Aug 27 at 15:27
1
According to the table it would take an input of size $17$ to run an $O(n!)$ algorithm for a century, not ~$10$
– SamYonnou
Aug 27 at 16:16
10
10
Yes, that's how the authors want us to read that table. It's mostly bogus, of course, since ignoring (potentially wildly different) constant factors makes the numbers meaningless. So we better ignore the specific numbers.
– Raphael♦
Aug 27 at 10:15
Yes, that's how the authors want us to read that table. It's mostly bogus, of course, since ignoring (potentially wildly different) constant factors makes the numbers meaningless. So we better ignore the specific numbers.
– Raphael♦
Aug 27 at 10:15
7
7
Yeah, the table is wrong actually. Yesterday, I ran an $O(n)$ algorithm for a month, and it didn't consume $2592cdot 10^9$ characters of input! In fact it only consumed $259198cdot 10^7$ characters.
– leftaroundabout
Aug 27 at 14:46
Yeah, the table is wrong actually. Yesterday, I ran an $O(n)$ algorithm for a month, and it didn't consume $2592cdot 10^9$ characters of input! In fact it only consumed $259198cdot 10^7$ characters.
– leftaroundabout
Aug 27 at 14:46
6
6
@Raphael Looks to me as if this is a table assuming you take f(n) microseconds, not just O (f(n)).
– gnasher729
Aug 27 at 15:25
@Raphael Looks to me as if this is a table assuming you take f(n) microseconds, not just O (f(n)).
– gnasher729
Aug 27 at 15:25
6
6
@leftaroundabout Yesterday you ran an algorithm for a month? With a bit of work you should be ready for a Nobel prize.
– gnasher729
Aug 27 at 15:27
@leftaroundabout Yesterday you ran an algorithm for a month? With a bit of work you should be ready for a Nobel prize.
– gnasher729
Aug 27 at 15:27
1
1
According to the table it would take an input of size $17$ to run an $O(n!)$ algorithm for a century, not ~$10$
– SamYonnou
Aug 27 at 16:16
According to the table it would take an input of size $17$ to run an $O(n!)$ algorithm for a century, not ~$10$
– SamYonnou
Aug 27 at 16:16
 |Â
show 7 more comments
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%2fcs.stackexchange.com%2fquestions%2f96661%2fwhy-does-n-have-the-least-time%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
15
This question is almost unclear, if the book mention was omitted. You never mentioned in the question what the numbers in the table is supposed to be.
– user92772
Aug 27 at 13:36
As shown by the comments under Josh Chen's answer, I'd say this question is very unclear. Please tell us what the book says about what the table represents.
– JiK
Aug 28 at 10:56
@JiK From the $n$ row, the tabulated values are the maximum $n$ such that $f(n)leq y$, where $f(n)$ is the function in the left column and $y$ is the number of milliseconds in the period of time stated at the top of hte column.
– David Richerby
Aug 28 at 12:53