Time and Space Complexity: Big-O Notation For students.

Time complexity counts how an algorithm's operations grow with input size; space complexity counts its extra memory. Big-O notation is the language for this growth: linear search is O(n) — doubling the list roughly doubles the work — while binary search is O(log n) — doubling adds just one step.

Hardware cannot save a bad algorithm. An O(n²) sort of a million records needs roughly a trillion operations, while O(n log n) needs about twenty million. In interviews and system design, Big-O compares solutions without running them.

Key Concepts

• Big-O (O): an upper bound — f(n) = O(g(n)) means f grows no faster than g, up to a constant, for large n.
• Big-Omega (Ω): a lower bound on growth. Big-Theta (Θ): a tight bound where both match.
• O(1): constant — array access, hash-table lookup.
• O(log n): doubling n adds a constant — binary search.
• O(n log n): efficient sorts like mergesort. O(n²): nested loops, e.g., bubble sort.
• O(2^n): exponential — brute-force subsets, naive Fibonacci.
• Dominant term rule: in 3n² + 10n + 5 only the fastest-growing term matters: O(n²).

Formulas

• Formal Big-O: f(n) = O(g(n)) if constants c > 0 and n0 exist with f(n) ≤ c·g(n) for all n ≥ n0.
• Sum rule: an O(n) step followed by an O(n²) step gives O(n²) — the worst part dominates.
• Product rule: an O(n) loop with an O(log n) inner operation gives O(n log n).
• Growth ladder: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n). For n = 1,000: log2 n ≈ 10, n log n ≈ 10,000, n² = 1,000,000.
• Space examples: iterative binary search O(1); mergesort O(n); recursion of depth d uses O(d) stack.
• Assumption: Big-O hides constant factors, so two O(n) algorithms can still differ 10× in practice.

Worked Example

Count pairs (i, j) with i < j in an array of size n: outer loop i from 0 to n−1, inner loop j from i+1 to n−1, O(1) work inside. For i = 0 the inner loop runs n−1 times, for i = 1 it runs n−2 times, and so on down to 0. Total = (n−1) + (n−2) + … + 1 = n(n−1)/2 = 0.5n² − 0.5n. Drop the constant and slower term → O(n²). For n = 10,000 that is ~50 million iterations — noticeably slow. Contrast: sorting once (O(n log n)) then answering 1,000 queries by binary search (O(log n) each) costs about 10,000 × 14 + 1,000 × 14 ≈ 154,000 operations versus 10 million with linear scans per query.

Common Misconceptions

• "O(n) is always faster than O(n²)." Only for large n — big constants let O(n²) win on small inputs, which is why quicksort uses insertion sort for tiny subarrays.
• "Big-O gives exact running time." Wrong. It describes growth shape, hiding constants; an O(n) algorithm with a 1-second step loses to O(n²) with a 1-nanosecond step on small n.
• "Memory is cheap, so space complexity is obsolete." Wrong at scale — O(n²) memory on a million items needs terabytes, and phones stay memory-tight.

Real-World Applications

• Interviews: almost every coding interview asks for time and space complexity.
• Database optimisers: join orders are picked using complexity estimates.
• System design: caching (O(1) lookup, O(n) memory) versus recomputation.
• Competitive programming: time limits (~10^8 ops/second) decide which complexity class passes.

Big-O is a pair of glasses for seeing how algorithms scale. Count the operations, keep the dominant term, drop the constants — and you can predict whether your code handles ten items or ten million before you press run.