咨询：当c>0时如何证明c f(n)∈Θ(f(n))
Hey there! You’ve got the right core idea—proving both ( c f(n) \in O(f(n)) ) and ( c f(n) \in \Omega(f(n)) ) is exactly how you get to ( c f(n) \in \Theta(f(n)) ). Let’s walk through each part with formal definitions to make it concrete.
First, let’s set our ground rules: we’ll assume ( c ) is a positive constant (since if ( c = 0 ), the result doesn’t hold for most non-bounded ( f(n) )), and ( f(n) ) is a non-negative function (standard for algorithm time/space complexity).
Proving ( c f(n) \in O(f(n)) )
Recall the formal definition of big-O notation:
A function ( g(n) ) is in ( O(f(n)) ) if there exist positive constants ( M ) and ( n_0 ) such that for all ( n \geq n_0 ), ( |g(n)| \leq M \cdot |f(n)| ).
Here, our ( g(n) = c f(n) ). Since ( f(n) ) is non-negative, we can drop the absolute values. Let’s pick:
- ( M = c )
- ( n_0 = 1 ) (any starting natural number works here)
For every ( n \geq 1 ), we have:
( c f(n) \leq c \cdot f(n) )
This is trivially true—equality holds for all ( n ). So we’ve satisfied the big-O condition, meaning ( c f(n) \in O(f(n)) ).
Proving ( c f(n) \in \Omega(f(n)) )
Now let’s use the definition of big-Ω:
A function ( g(n) ) is in ( \Omega(f(n)) ) if there exist positive constants ( K ) and ( n_0 ) such that for all ( n \geq n_0 ), ( |g(n)| \geq K \cdot |f(n)| ).
Again, ( g(n) = c f(n) ), and we can ignore absolute values. Let’s choose:
- ( K = c )
- ( n_0 = 1 )
For every ( n \geq 1 ):
( c f(n) \geq c \cdot f(n) )
Just like before, this is always true (equality holds). So we’ve met the big-Ω requirement, so ( c f(n) \in \Omega(f(n)) ).
Wrapping Up to Get ( c f(n) \in \Theta(f(n)) )
By definition, a function is in ( \Theta(f(n)) ) if and only if it is in both ( O(f(n)) ) and ( \Omega(f(n)) ). Since we’ve proven both conditions hold for ( c f(n) ), we can conclude:
( c f(n) \in \Theta(f(n)) )
Quick side note: If ( c = 0 ), ( 0 \cdot f(n) = 0 ). This is in ( O(f(n)) ) (since 0 is always ≤ some multiple of ( f(n) ) for large ( n )), but it’s not in ( \Omega(f(n)) ) (unless ( f(n) ) is bounded, which isn’t typical for complexity functions). So the result only holds when ( c > 0 ), which is the case we care about for algorithm analysis.
内容的提问来源于stack exchange，提问作者Neil Ma
