Big O Notation

overview

Summary

Big O notation describes how an algorithm’s running time or space grows with input size n. It gives an upper bound, ignoring constant factors and lower-order terms, to compare scalability. Common classes include O(1), O(log n), O(n), O(n log n), and O(n^2). Use it to estimate worst-case cost, choose appropriate data structures, and reason about tradeoffs. Remember that Big Theta (Θ) gives a tight bound and Omega (Ω) a lower bound, while real performance also depends on constants and hardware.