What is Big O Notation?
Big O notation describes the upper bound of an algorithm's growth rate. It tells us how an algorithm's time or space requirements grow as the input size (n) increases.
O(f(n))
Upper bound (worst case)
Ω(f(n))
Lower bound (best case)
Θ(f(n))
Tight bound (both)
Why Big O Matters
Scalability
Predict how performance degrades with larger inputs
Comparison
Compare algorithms objectively regardless of hardware
Optimization
Identify bottlenecks and optimization opportunities
Interview Prep
Essential for technical coding interviews
Growth Rate Comparison
n=10: O(1) O(log n) O(n) O(n log n) O(n²) O(2^n)
████ █████ ██████ ████████ ██████████████ ████████████████████████████████████████
n=100: O(1) O(log n) O(n) O(n log n) O(n²) O(2^n)
████ █████ ████████████████ ████████████████████████████████████ █████████████████████████████████████████████████ O(1) Constant - Always fast
█ O(log n) Logarithmic - Very scalable
█ O(n) Linear - Grows proportionally
█ O(n log n) Linearithmic - Merge/Quick sort
█ O(n²) Quadratic - Nested loops
█ O(2^n) Exponential - Avoid!
Key Rules
Drop Constants
O(2n + 5) → O(n). Constants don't matter in asymptotic analysis.
Drop Lower Order Terms
O(n² + n + 1) → O(n²). Keep only the dominant term.
Base of Log Doesn't Matter
O(log₂ n) = O(log₁₀ n) = O(log n). All logarithms grow similarly.