0

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

wu binhao
  • 11
  • 1
  • 6
  • 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 '18 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 '18 at 19:09
  • no the smallest input length. *n* is the length of input. – Willem Van Onsem Nov 10 '18 at 19:09
  • I would have expected something like "n >= n0", not like it is quoted here. Is the quote correct? – trincot Nov 10 '18 at 19:31
  • @trincot Oh yes, sorry i just realized i typed the quote wrong! I will correct it now. – wu binhao Nov 10 '18 at 19:35
  • It means that the other condition must be true for all *n* above some minimum value *n0*. You can select that value yourself, as long as it makes the statement about *n* true for *all* greater *n*. And of course, if you find a value *n0* with that property, you could also have selected *n[0]+100*, or anything greater. – trincot Nov 10 '18 at 19:38
  • @trincot thanks! now it made sense for me. – wu binhao Nov 10 '18 at 19:43
  • Possible duplicate of [When something is Big O, does it mean that it is exactly the result of Big O?](https://stackoverflow.com/questions/53240689/when-something-is-big-o-does-it-mean-that-it-is-exactly-the-result-of-big-o) – Zabuzard Nov 10 '18 at 19:44

1 Answers1

4

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065