大O（Big O）复杂度分析疑问：上界来源、方法及公式意义

Let’s break down each of your questions step by step to clarify how Big O works—both intuitively and mathematically.

1. Where does the upper-bound function g(n) come from? #

The function g(n) is a benchmark growth function we use to describe the asymptotic behavior of your program’s complexity function f(n). It’s chosen based on the fastest-growing term in f(n): since Big O focuses on how complexity scales as input size n approaches infinity, lower-order terms and constants become negligible.

For example, in f(n) = 5n + 3, the term 5n grows far faster than the constant 3 as n gets large. So we pick g(n) = n (the simplest function that matches this core growth rate) as our upper bound. Common g(n) functions come from standard complexity classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), etc.

2. Does the "drop lower-order terms and constants" method work for all programs? #

Absolutely—this simplification is a direct result of Big O’s mathematical definition, so it applies whenever you can derive an explicit complexity function f(n) for a program.

That said, some programs (like recursive divide-and-conquer algorithms) don’t have obvious polynomial f(n) expressions at first glance. For those, you might need tools like the Master Theorem or recursion trees to calculate f(n) first. But once you have f(n), the rule holds: lower-order terms and constants don’t affect the asymptotic growth rate, so we discard them to get the Big O classification.

3. What’s the purpose of the formal definition F(N) ≤ C*G(N)? #

This inequality is the rigorous mathematical foundation of Big O notation. The "drop terms" shortcut is just a heuristic derived from this definition—but the formal rule is what lets us prove our intuitive classification is correct.

It eliminates ambiguity: instead of just saying "5n+3 grows like n," we can mathematically show that n is indeed an upper bound for f(n) once n is large enough. This is critical for edge cases where intuition might fail, or when you need to verify complexity claims in formal or academic settings.

4. How to verify f(n) = 5n + 3 is O(n) using the formal definition? #

To prove f(n) ∈ O(g(n)), we need to find two positive constants:

• A scaling factor C for g(n)
• A threshold N₀ such that the inequality holds for all n ≥ N₀

Let’s apply this to f(n) = 5n + 3 and g(n) = n:

1. Start with the required inequality: 5n + 3 ≤ C * n
2. Rearrange to solve for C: 5 + 3/n ≤ C
3. As n approaches infinity, 3/n approaches 0. Let’s pick a simple valid C, like 6.
4. Now find N₀ where 5n + 3 ≤ 6n holds:

   5n + 3 ≤ 6n
   3 ≤ n
   

   So N₀ = 3.

For all n ≥ 3, the inequality holds:

• When n=3: 53+3=18, 63=18 (equal)
• When n=4: 54+3=23 ≤ 64=24 (true)
• As n grows, the gap between 6n and 5n+3 increases, so the inequality will always hold.

This satisfies the formal definition, so we can confidently say f(n) = O(n).

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