Importance of growth function; Theta, O, Omega

Importance of growth functions

A growth function (order of growth) describes how the running time or memory use of an algorithm increases as the input size n increases. It matters because:

• It lets us compare algorithms independent of hardware and language.
• For large n, the fastest-growing term dominates, so constants and lower terms can be dropped.
• It predicts scalability: doubling n makes an O(n) algorithm take 2× time, but an O(n²) algorithm 4× time and an O(2ⁿ) algorithm impractical.
• It guides the choice of algorithm and data structure before implementation.

Common orders: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!.

Big-Oh (O): upper bound

f(n) = O(g(n)) if f(n) ≤ c·g(n) for all n ≥ n₀ (c, n₀ > 0). Used for the worst case. Example: 3n + 2 = O(n).

Omega (Ω): lower bound

f(n) = Ω(g(n)) if f(n) ≥ c·g(n) for all n ≥ n₀. Used for the best-case or minimum work. Example: 3n + 2 = Ω(n).

Theta (Θ): tight bound

f(n) = Θ(g(n)) if c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀. It means f is both O(g) and Ω(g). Example: 3n + 2 = Θ(n).