Division operation on asymptotic notation

问题:

Suppose

S(n) = Big-Oh(f(n)) & T(n) = Big-Oh(f(n)) 

both f(n) identically belongs from the same class.

My ques is: Why S(n)/T(n) = Big-Oh(1) is incorrect?

回答1:

Consider S(n) = n^2 and T(n) = n. Then both S and T are O(n^2) but S(n) / T(n) = n which is not O(1).

Here's another example. Consider S(n) = sin(n) and T(n) = cos(n). Then S and T are O(1) but S(n) / T(n) = tan(n) is not O(1). This second example is important because it shows that even if you have a tight bound, the conclusion can still fail.

Why is this happening? Because the obvious "proof" completely fails. The obvious "proof" is the following. There are constants C_S and C_T and N_S and N_T where n >= N_S implies |S(n)| <= C_S * f(n) and n >= N_T implies |T(n)| <= C_T * f(n). Let N = max(N_S, N_T). Then for n >= N we have

|S(n) / T(n)| <= (C_S * f(n)) / (C_T * f(n)) = C_S / C_T.

This is completely and utterly wrong. It is not the case that |T(n)| <= C_T * f(n) implies that 1 / |T(n)| <= 1 / (C_T * f(n)). In fact, what is true is that 1 / |T(n)| >= 1 / (C_T * f(n)). The inequality reverses, and that suggests there is a serious problem with the "theorem." The intuitive idea is that if T is "small" (i.e., bounded) then 1 / T is "big." But we're trying to show that 1 / T is "small" and we just can't do that. As our counterexamples show, the "proof" is fatally flawed.

However, there is a theorem here that is true. Namely, if S(n) is O(f(n)) and T(n) is Ω(f(n)), then S(n) / T(n) is O(1). The above "proof" works for this theorem (thanks are due to Simone for the idea to generalize to this statement).

回答2:

Here's one counter example:

Let's say f(n) = n^2, S(n) = n^2 and T(n) = n. Now both S and T are in O(f(n)) (you have to remember that O(n^2) is a superset of O(n), so everything that's in O(n) is also in O(n^2)), but U(n) = S(n)/T(n) = n^2/n = n is definitely not in O(1).

回答3:

Like the others explained S(n) / T(n) is not generally O(1).

Your doubt probably derive from the confusion between O and Θ; in fact if:

S(n) = Θ(n)      and      T(n) = Θ(n)

then the following is true:

S(n) / T(n) = Θ(1)  and thus S(n) / T(n) = O(1)

回答4:

You can prove that this is wrong if you plug some actual functions into your formula, e.g.

S(n) = n^2
T(n) = n
f(n) = n^2

S(n) / T(n) = n
n != O(1)