gen-define-asymptotic-big-o-complexity-and-give-one-short-worked-b63f

Define asymptotic (big-O) complexity and give one short worked example.

# Asymptotic (Big-O) Complexity **Definition:** Big-O notation describes the **upper bound** of an algorithm's growth rate as input size approaches infinity. We say f(n) = O(g(n)) if there exist positive constants c and n₀ such that: **f(n) ≤ c · g(n)** for all n ≥ n₀ In simpler terms: Big-O tells us the worst-case scenario for how runtime/space grows with input size, ignoring constant factors and lower-order terms. ## Worked Example **Problem:** Find the Big-O complexity of this function: ``` f(n) = 3n² + 5n + 10 ``` **Solution:** 1. **Identify the dominant term:** As n grows large, n² grows much faster than n or constants - When n = 100: 3(10,000) vs 5(100) vs 10 - The n² term dominates 2. **Drop constants and lower-order terms:** - f(n) = 3n² + 5n + 10 - Drop coefficient: ~~3~~n² - Drop smaller terms: n² ~~+ 5n + 10~~ 3. **Result:** **f(n) = O(n²)** **Verification:** We need f(n) ≤ c·n² for some c and large enough n. - Choose c = 4 and n₀ = 10 - For n ≥ 10: 3n² + 5n + 10 ≤ 3n² + n² = 4n² ✓ Therefore, the algorithm has **quadratic complexity**.