Big O符号相关技术咨询：命题真伪判断及是否符合传递性规则

Hey there! Let's work through your questions clearly since you're just diving into Big O notation—totally normal to hit these confusion points early on!

Short answer: No, this proposition does not hold in general.

To understand why, let's start with the formal definition of Big O notation:

A function ( g(n) ) is said to be ( O(f(n)) ) if there exist constants ( C > 0 ) and ( n_0 \geq 0 ) such that for all ( n \geq n_0 ), ( |g(n)| \leq C \cdot |f(n)| ). In plain terms, ( g ) grows no faster than a constant multiple of ( f ) as ( n ) gets very large.

Now let's use a concrete counterexample to disprove the proposition:

• Let ( f(n) = n ) (linear growth)
• Let ( g(n) = n ) (also linear)
• Let ( h(n) = 1 ) (constant growth)

First, check the premises:

• ( g(n) = n ) is ( O(f(n)) ): Pick ( C=1 ) and ( n_0=1 )—for all ( n \geq 1 ), ( n \leq 1 \cdot n ), which is true.
• ( h(n) = 1 ) is ( O(f(n)) ): Pick ( C=1 ) and ( n_0=1 )—for all ( n \geq 1 ), ( 1 \leq 1 \cdot n ), which is also true.

Now check the conclusion: Is ( g(n) = n ) ( O(h(n)) = O(1) )?
For ( n ) to be ( O(1) ), we'd need some constant ( C ) where ( n \leq C \cdot 1 ) for all sufficiently large ( n ). But as ( n ) grows, it will always exceed any fixed ( C )—so this is impossible.

This counterexample shows the proposition fails: even though both ( g ) and ( h ) are upper-bounded by ( f ), ( g ) can grow much faster than ( h ), making ( g = O(h) ) false.

No, it does not—this proposition is unrelated to Big O's transitive property, and in fact, it contradicts how transitivity works.

Big O's transitivity is a well-established rule that says:

If ( a = O(b) ) and ( b = O(c) ), then ( a = O(c) ).

This is a "chain" relationship: ( a ) is bounded by ( b ), which is bounded by ( c ), so ( a ) must be bounded by ( c ). Your proposition, however, is a "fork" relationship: both ( g ) and ( h ) are bounded by ( f ), but there's no chain linking ( g ) to ( h ) through ( f ). Transitivity doesn't apply here, as we saw with the counterexample above.

Quick recap to solidify #

• Big O describes an asymptotic upper bound, not a direct comparison between every pair of functions that share a common upper bound.
• Transitivity only applies when you have a sequence of bounded functions (A → B → C), not when two functions both bound to a third (A ← C → B).

内容的提问来源于stack exchange，提问作者Marrykittens