What is the value of n0?
up vote
0
down vote
favorite
Just started learning algorithm. But, I don't know what n0 represent in calculating time complexity.
Full quoto for the mergeSort time complexity.
Ө(nlogn) - C1 * nlogn <= T(n) <= C2 * logn, if n >= n0
O(nlogn) - T(n) <= C * nlogn, if n >= n0
algorithm time-complexity big-o
asked Nov 10 at 19:05
wu binhao
63
|
show 3 more comments
up vote
0
down vote
favorite
Just started learning algorithm. But, I don't know what n0 represent in calculating time complexity.
Full quoto for the mergeSort time complexity.
Ө(nlogn) - C1 * nlogn <= T(n) <= C2 * logn, if n >= n0
O(nlogn) - T(n) <= C * nlogn, if n >= n0
algorithm time-complexity big-o
asked Nov 10 at 19:05
wu binhao
63
Probalbyn0is the first number where an assymptotically better algorithm is better than its "competitor". But it might be worth to quote the full definition, theorem, etc.
– Willem Van Onsem
Nov 10 at 19:06
Sorry, could you simplify what you said? I still don't get it. What is the "first number" is it the first element in an array?
– wu binhao
Nov 10 at 19:09
no the smallest input length. n is the length of input.
– Willem Van Onsem
Nov 10 at 19:09
I would have expected something like "n >= n0", not like it is quoted here. Is the quote correct?
– trincot
Nov 10 at 19:31
@trincot Oh yes, sorry i just realized i typed the quote wrong! I will correct it now.
– wu binhao
Nov 10 at 19:35
|
show 3 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Just started learning algorithm. But, I don't know what n0 represent in calculating time complexity.
Full quoto for the mergeSort time complexity.
Ө(nlogn) - C1 * nlogn <= T(n) <= C2 * logn, if n >= n0
O(nlogn) - T(n) <= C * nlogn, if n >= n0
algorithm time-complexity big-o
asked Nov 10 at 19:05
wu binhao
63
Just started learning algorithm. But, I don't know what n0 represent in calculating time complexity.
Full quoto for the mergeSort time complexity.
Ө(nlogn) - C1 * nlogn <= T(n) <= C2 * logn, if n >= n0
O(nlogn) - T(n) <= C * nlogn, if n >= n0
algorithm time-complexity big-o
algorithm time-complexity big-o
asked Nov 10 at 19:05
wu binhao
63
asked Nov 10 at 19:05
wu binhao
63
edited Nov 10 at 19:39
asked Nov 10 at 19:05
wu binhao
63
asked Nov 10 at 19:05
wu binhao
63
asked Nov 10 at 19:05
wu binhao
63
63
Probalbyn0is the first number where an assymptotically better algorithm is better than its "competitor". But it might be worth to quote the full definition, theorem, etc.
– Willem Van Onsem
Nov 10 at 19:06
Sorry, could you simplify what you said? I still don't get it. What is the "first number" is it the first element in an array?
– wu binhao
Nov 10 at 19:09
no the smallest input length. n is the length of input.
– Willem Van Onsem
Nov 10 at 19:09
I would have expected something like "n >= n0", not like it is quoted here. Is the quote correct?
– trincot
Nov 10 at 19:31
@trincot Oh yes, sorry i just realized i typed the quote wrong! I will correct it now.
– wu binhao
Nov 10 at 19:35
|
show 3 more comments
Probalbyn0is the first number where an assymptotically better algorithm is better than its "competitor". But it might be worth to quote the full definition, theorem, etc.
– Willem Van Onsem
Nov 10 at 19:06
Sorry, could you simplify what you said? I still don't get it. What is the "first number" is it the first element in an array?
– wu binhao
Nov 10 at 19:09
no the smallest input length. n is the length of input.
– Willem Van Onsem
Nov 10 at 19:09
I would have expected something like "n >= n0", not like it is quoted here. Is the quote correct?
– trincot
Nov 10 at 19:31
@trincot Oh yes, sorry i just realized i typed the quote wrong! I will correct it now.
– wu binhao
Nov 10 at 19:35
Probalby
n0 is the first number where an assymptotically better algorithm is better than its "competitor". But it might be worth to quote the full definition, theorem, etc.– Willem Van Onsem
Nov 10 at 19:06
Probalby
n0 is the first number where an assymptotically better algorithm is better than its "competitor". But it might be worth to quote the full definition, theorem, etc.– Willem Van Onsem
Nov 10 at 19:06
Sorry, could you simplify what you said? I still don't get it. What is the "first number" is it the first element in an array?
– wu binhao
Nov 10 at 19:09
Sorry, could you simplify what you said? I still don't get it. What is the "first number" is it the first element in an array?
– wu binhao
Nov 10 at 19:09
no the smallest input length. n is the length of input.
– Willem Van Onsem
Nov 10 at 19:09
no the smallest input length. n is the length of input.
– Willem Van Onsem
Nov 10 at 19:09
I would have expected something like "n >= n0", not like it is quoted here. Is the quote correct?
– trincot
Nov 10 at 19:31
I would have expected something like "n >= n0", not like it is quoted here. Is the quote correct?
– trincot
Nov 10 at 19:31
@trincot Oh yes, sorry i just realized i typed the quote wrong! I will correct it now.
– wu binhao
Nov 10 at 19:35
@trincot Oh yes, sorry i just realized i typed the quote wrong! I will correct it now.
– wu binhao
Nov 10 at 19:35
|
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
3
down vote
Intuitively speaking, the statement f(n) = O(g(n)) means
For any sufficiently large value of n, the value of f(n) is bounded from above by a constant multiple of g(n).
In other words, although f(n) might initially start off significantly larger than g(n), in the long-run, you'll find that f(n) is eventually matched, or overtaken, by some constant multiple of g(n).
The n0 you're referring to here is the formal mathematical way of pinning down this idea of "sufficiently large." Specifically, if the claim being made is
T(n) ≤ C2 n log n, if n ≥ n0,
the value n0 is some cutoff threshold. That is, it's the point where we say that n is "sufficiently large."
The particular choice of n0 and C2 in the above statements will depend on the particular problem that you're working through, but hopefully this gives you a sense of how to interpret what you're looking at.
answered Nov 10 at 19:44
templatetypedef
258k66652881
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Intuitively speaking, the statement f(n) = O(g(n)) means
For any sufficiently large value of n, the value of f(n) is bounded from above by a constant multiple of g(n).
In other words, although f(n) might initially start off significantly larger than g(n), in the long-run, you'll find that f(n) is eventually matched, or overtaken, by some constant multiple of g(n).
The n0 you're referring to here is the formal mathematical way of pinning down this idea of "sufficiently large." Specifically, if the claim being made is
T(n) ≤ C2 n log n, if n ≥ n0,
the value n0 is some cutoff threshold. That is, it's the point where we say that n is "sufficiently large."
The particular choice of n0 and C2 in the above statements will depend on the particular problem that you're working through, but hopefully this gives you a sense of how to interpret what you're looking at.
answered Nov 10 at 19:44
templatetypedef
258k66652881
add a comment |
up vote
3
down vote
Intuitively speaking, the statement f(n) = O(g(n)) means
For any sufficiently large value of n, the value of f(n) is bounded from above by a constant multiple of g(n).
In other words, although f(n) might initially start off significantly larger than g(n), in the long-run, you'll find that f(n) is eventually matched, or overtaken, by some constant multiple of g(n).
The n0 you're referring to here is the formal mathematical way of pinning down this idea of "sufficiently large." Specifically, if the claim being made is
T(n) ≤ C2 n log n, if n ≥ n0,
the value n0 is some cutoff threshold. That is, it's the point where we say that n is "sufficiently large."
The particular choice of n0 and C2 in the above statements will depend on the particular problem that you're working through, but hopefully this gives you a sense of how to interpret what you're looking at.
answered Nov 10 at 19:44
templatetypedef
258k66652881
add a comment |
up vote
3
down vote
up vote
3
down vote
Intuitively speaking, the statement f(n) = O(g(n)) means
For any sufficiently large value of n, the value of f(n) is bounded from above by a constant multiple of g(n).
In other words, although f(n) might initially start off significantly larger than g(n), in the long-run, you'll find that f(n) is eventually matched, or overtaken, by some constant multiple of g(n).
The n0 you're referring to here is the formal mathematical way of pinning down this idea of "sufficiently large." Specifically, if the claim being made is
T(n) ≤ C2 n log n, if n ≥ n0,
the value n0 is some cutoff threshold. That is, it's the point where we say that n is "sufficiently large."
The particular choice of n0 and C2 in the above statements will depend on the particular problem that you're working through, but hopefully this gives you a sense of how to interpret what you're looking at.
answered Nov 10 at 19:44
templatetypedef
258k66652881
Intuitively speaking, the statement f(n) = O(g(n)) means
For any sufficiently large value of n, the value of f(n) is bounded from above by a constant multiple of g(n).
In other words, although f(n) might initially start off significantly larger than g(n), in the long-run, you'll find that f(n) is eventually matched, or overtaken, by some constant multiple of g(n).
The n0 you're referring to here is the formal mathematical way of pinning down this idea of "sufficiently large." Specifically, if the claim being made is
T(n) ≤ C2 n log n, if n ≥ n0,
the value n0 is some cutoff threshold. That is, it's the point where we say that n is "sufficiently large."
The particular choice of n0 and C2 in the above statements will depend on the particular problem that you're working through, but hopefully this gives you a sense of how to interpret what you're looking at.
answered Nov 10 at 19:44
templatetypedef
258k66652881
answered Nov 10 at 19:44
templatetypedef
258k66652881
answered Nov 10 at 19:44
templatetypedef
258k66652881
answered Nov 10 at 19:44
templatetypedef
258k66652881
258k66652881
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53242443%2fwhat-is-the-value-of-n0%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
Probalby
n0is the first number where an assymptotically better algorithm is better than its "competitor". But it might be worth to quote the full definition, theorem, etc.– Willem Van Onsem
Nov 10 at 19:06
Sorry, could you simplify what you said? I still don't get it. What is the "first number" is it the first element in an array?
– wu binhao
Nov 10 at 19:09
no the smallest input length. n is the length of input.
– Willem Van Onsem
Nov 10 at 19:09
I would have expected something like "n >= n0", not like it is quoted here. Is the quote correct?
– trincot
Nov 10 at 19:31
@trincot Oh yes, sorry i just realized i typed the quote wrong! I will correct it now.
– wu binhao
Nov 10 at 19:35