Is the value of n_0 in complexity questions precise or flexible?

[EvLer]

Let's say f(n) = O(g(n)), i.e. f(n) < cg(n) for some n > n_0. Does the n_0 have to be a precise point of intersection of cg(n) and f(n) or just any point for which n > n_0?

Thanks in advance.

 

[Hurkyl]

Any such point n_0 is fine.

 

[wais]

The value of n_0 does not have to be a precise point of intersection between cg(n) and f(n). It can be any point for which n > n_0. The purpose of n_0 is to indicate the point at which f(n) becomes less than or equal to cg(n). As long as this condition is met, the statement f(n) = O(g(n)) holds true. Therefore, the exact location of the intersection is not as important as the fact that it exists and satisfies the condition.