CODEWITHSUNDEEP
algorithmtime-complexitybig-o
wu binhao
wu binhao

Reputation: 11

What is the value of n0?

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

Upvotes: 0

Views: 2183

Answers (1)

templatetypedef
templatetypedef

Reputation: 373112

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.

Upvotes: 4

Related Questions