How can two algorithms one with O(n^2) the other Ω(n) has about the same run time?
up vote
0
down vote
favorite
How can two algorithms
- one with
O(n²) - the other with
Ω(n)
have the same practical run time, when testing the algorithms with a large number?
big-o complexity-theory
edited Nov 10 at 14:54
Cœur
17.2k9102142
asked May 6 '15 at 17:03
user3456374
163
|
show 5 more comments
up vote
0
down vote
favorite
How can two algorithms
- one with
O(n²) - the other with
Ω(n)
have the same practical run time, when testing the algorithms with a large number?
big-o complexity-theory
edited Nov 10 at 14:54
Cœur
17.2k9102142
asked May 6 '15 at 17:03
user3456374
163
16
How can someone whose height is greater than 1 meter be just as tall as someone whose height is less than 3 meters?
– Douglas Zare
May 6 '15 at 17:04
Big-O notation doesn't account for the coefficients. If the "faster" algorithm has a higher coefficient, you may need very large inputs for it to overtake the slower algorithm.
– Barmar
May 6 '15 at 17:06
1
This isn't even a question of coefficients; the OP is trying to compare worst-case running time to best-case running time.
– chepner
May 6 '15 at 17:17
@chepner, it's not about coefficient, but also not about worst/best-case distinction. O and Omega can both be applied to best/average/worst case runtime or any other function.
– zch
May 6 '15 at 17:28
dupe: stackoverflow.com/q/29972024/572670 (Don't want to single handedly close as dupe as I am the answerer, but it's basically a dupe)
– amit
May 6 '15 at 17:30
|
show 5 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
How can two algorithms
- one with
O(n²) - the other with
Ω(n)
have the same practical run time, when testing the algorithms with a large number?
big-o complexity-theory
edited Nov 10 at 14:54
Cœur
17.2k9102142
asked May 6 '15 at 17:03
user3456374
163
How can two algorithms
- one with
O(n²) - the other with
Ω(n)
have the same practical run time, when testing the algorithms with a large number?
big-o complexity-theory
big-o complexity-theory
edited Nov 10 at 14:54
Cœur
17.2k9102142
asked May 6 '15 at 17:03
user3456374
163
edited Nov 10 at 14:54
Cœur
17.2k9102142
asked May 6 '15 at 17:03
user3456374
163
edited Nov 10 at 14:54
Cœur
17.2k9102142
edited Nov 10 at 14:54
Cœur
17.2k9102142
edited Nov 10 at 14:54
Cœur
17.2k9102142
17.2k9102142
asked May 6 '15 at 17:03
user3456374
163
asked May 6 '15 at 17:03
user3456374
163
asked May 6 '15 at 17:03
user3456374
163
163
16
How can someone whose height is greater than 1 meter be just as tall as someone whose height is less than 3 meters?
– Douglas Zare
May 6 '15 at 17:04
Big-O notation doesn't account for the coefficients. If the "faster" algorithm has a higher coefficient, you may need very large inputs for it to overtake the slower algorithm.
– Barmar
May 6 '15 at 17:06
1
This isn't even a question of coefficients; the OP is trying to compare worst-case running time to best-case running time.
– chepner
May 6 '15 at 17:17
@chepner, it's not about coefficient, but also not about worst/best-case distinction. O and Omega can both be applied to best/average/worst case runtime or any other function.
– zch
May 6 '15 at 17:28
dupe: stackoverflow.com/q/29972024/572670 (Don't want to single handedly close as dupe as I am the answerer, but it's basically a dupe)
– amit
May 6 '15 at 17:30
|
show 5 more comments
16
How can someone whose height is greater than 1 meter be just as tall as someone whose height is less than 3 meters?
– Douglas Zare
May 6 '15 at 17:04
Big-O notation doesn't account for the coefficients. If the "faster" algorithm has a higher coefficient, you may need very large inputs for it to overtake the slower algorithm.
– Barmar
May 6 '15 at 17:06
1
This isn't even a question of coefficients; the OP is trying to compare worst-case running time to best-case running time.
– chepner
May 6 '15 at 17:17
@chepner, it's not about coefficient, but also not about worst/best-case distinction. O and Omega can both be applied to best/average/worst case runtime or any other function.
– zch
May 6 '15 at 17:28
dupe: stackoverflow.com/q/29972024/572670 (Don't want to single handedly close as dupe as I am the answerer, but it's basically a dupe)
– amit
May 6 '15 at 17:30
16
16
How can someone whose height is greater than 1 meter be just as tall as someone whose height is less than 3 meters?
– Douglas Zare
May 6 '15 at 17:04
How can someone whose height is greater than 1 meter be just as tall as someone whose height is less than 3 meters?
– Douglas Zare
May 6 '15 at 17:04
Big-O notation doesn't account for the coefficients. If the "faster" algorithm has a higher coefficient, you may need very large inputs for it to overtake the slower algorithm.
– Barmar
May 6 '15 at 17:06
Big-O notation doesn't account for the coefficients. If the "faster" algorithm has a higher coefficient, you may need very large inputs for it to overtake the slower algorithm.
– Barmar
May 6 '15 at 17:06
1
1
This isn't even a question of coefficients; the OP is trying to compare worst-case running time to best-case running time.
– chepner
May 6 '15 at 17:17
This isn't even a question of coefficients; the OP is trying to compare worst-case running time to best-case running time.
– chepner
May 6 '15 at 17:17
@chepner, it's not about coefficient, but also not about worst/best-case distinction. O and Omega can both be applied to best/average/worst case runtime or any other function.
– zch
May 6 '15 at 17:28
@chepner, it's not about coefficient, but also not about worst/best-case distinction. O and Omega can both be applied to best/average/worst case runtime or any other function.
– zch
May 6 '15 at 17:28
dupe: stackoverflow.com/q/29972024/572670 (Don't want to single handedly close as dupe as I am the answerer, but it's basically a dupe)
– amit
May 6 '15 at 17:30
dupe: stackoverflow.com/q/29972024/572670 (Don't want to single handedly close as dupe as I am the answerer, but it's basically a dupe)
– amit
May 6 '15 at 17:30
|
show 5 more comments
1 Answer
1
active
oldest
votes
up vote
2
down vote
O(f(n)) is a set of functions that grow proportionally to f(n) or slower.
Ω(f(n)) is a set of functions that grow proportionally to f(n) or faster.
There are many functions that grow at least as fast as n, but not faster than n^2. For example: n, n*log n, n^1.5, n^2.
answered May 6 '15 at 17:14
zch
12.1k23046
And when you compare a specific (smaller) n the linear factors matter for both as well.
– eckes
May 6 '15 at 19:24
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
O(f(n)) is a set of functions that grow proportionally to f(n) or slower.
Ω(f(n)) is a set of functions that grow proportionally to f(n) or faster.
There are many functions that grow at least as fast as n, but not faster than n^2. For example: n, n*log n, n^1.5, n^2.
answered May 6 '15 at 17:14
zch
12.1k23046
And when you compare a specific (smaller) n the linear factors matter for both as well.
– eckes
May 6 '15 at 19:24
add a comment |
up vote
2
down vote
O(f(n)) is a set of functions that grow proportionally to f(n) or slower.
Ω(f(n)) is a set of functions that grow proportionally to f(n) or faster.
There are many functions that grow at least as fast as n, but not faster than n^2. For example: n, n*log n, n^1.5, n^2.
answered May 6 '15 at 17:14
zch
12.1k23046
And when you compare a specific (smaller) n the linear factors matter for both as well.
– eckes
May 6 '15 at 19:24
add a comment |
up vote
2
down vote
up vote
2
down vote
O(f(n)) is a set of functions that grow proportionally to f(n) or slower.
Ω(f(n)) is a set of functions that grow proportionally to f(n) or faster.
There are many functions that grow at least as fast as n, but not faster than n^2. For example: n, n*log n, n^1.5, n^2.
answered May 6 '15 at 17:14
zch
12.1k23046
O(f(n)) is a set of functions that grow proportionally to f(n) or slower.
Ω(f(n)) is a set of functions that grow proportionally to f(n) or faster.
There are many functions that grow at least as fast as n, but not faster than n^2. For example: n, n*log n, n^1.5, n^2.
answered May 6 '15 at 17:14
zch
12.1k23046
answered May 6 '15 at 17:14
zch
12.1k23046
answered May 6 '15 at 17:14
zch
12.1k23046
answered May 6 '15 at 17:14
zch
12.1k23046
12.1k23046
And when you compare a specific (smaller) n the linear factors matter for both as well.
– eckes
May 6 '15 at 19:24
add a comment |
And when you compare a specific (smaller) n the linear factors matter for both as well.
– eckes
May 6 '15 at 19:24
And when you compare a specific (smaller) n the linear factors matter for both as well.
– eckes
May 6 '15 at 19:24
And when you compare a specific (smaller) n the linear factors matter for both as well.
– eckes
May 6 '15 at 19:24
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f30083171%2fhow-can-two-algorithms-one-with-on2-the-other-%25ce%25a9n-has-about-the-same-run-tim%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
16
How can someone whose height is greater than 1 meter be just as tall as someone whose height is less than 3 meters?
– Douglas Zare
May 6 '15 at 17:04
Big-O notation doesn't account for the coefficients. If the "faster" algorithm has a higher coefficient, you may need very large inputs for it to overtake the slower algorithm.
– Barmar
May 6 '15 at 17:06
1
This isn't even a question of coefficients; the OP is trying to compare worst-case running time to best-case running time.
– chepner
May 6 '15 at 17:17
@chepner, it's not about coefficient, but also not about worst/best-case distinction. O and Omega can both be applied to best/average/worst case runtime or any other function.
– zch
May 6 '15 at 17:28
dupe: stackoverflow.com/q/29972024/572670 (Don't want to single handedly close as dupe as I am the answerer, but it's basically a dupe)
– amit
May 6 '15 at 17:30