Big-O notation is the standard mathematical language developers use to describe how an algorithm's runtime or memory usage grows relative to its input size. Mastering it lets you compare algorithms objectively and write code that scales.
Big-O notation expresses the upper bound of an algorithm's growth rate as a function of input size n. It answers the question: as n gets very large, how does the cost (time or space) scale? The 'O' stands for 'Order of' and the expression inside the parentheses describes that growth curve. It deliberately ignores constant factors and lower-order terms to focus on dominant behavior at scale.
Choosing the wrong algorithm can turn a millisecond operation into one that runs for hours when data grows from thousands to millions of records. Big-O gives you a hardware-agnostic way to reason about performance before writing or benchmarking code. It is the shared vocabulary used in code reviews, system design interviews, and architecture discussions worldwide.
O(1) is constant time — the operation takes the same time regardless of n, like a hash-map lookup. O(log n) is logarithmic and typical of binary search, while O(n) is linear and seen in a single-pass array scan. O(n log n) describes efficient sorting algorithms like merge sort, O(n²) appears in nested loops over the same data, and O(2ⁿ) signals exponential growth found in naive recursive solutions like brute-force subset enumeration.
To find Big-O, count the number of basic operations as a function of n, then keep only the fastest-growing term and drop its coefficient. For example, an algorithm doing 3n² + 5n + 42 operations is O(n²) because n² dominates as n approaches infinity. Nested loops that each iterate over n elements multiply their complexities, giving O(n²), while a loop that halves its search space each iteration yields O(log n).
Big-O most commonly describes the worst-case scenario, which sets a hard ceiling on how bad performance can get. Best-case is expressed with Omega (Ω) notation and average-case with Theta (Θ) notation. Quick sort, for example, is O(n log n) on average but degrades to O(n²) in the worst case when the pivot is always the smallest or largest element. Always clarify which case you are discussing to avoid misleading performance claims.
Big-O deliberately hides constants, but those constants can dominate for small or medium n values that are common in real applications. An O(n log n) algorithm with a large constant may outperform an O(n) algorithm for n under a few thousand. Always benchmark with realistic data sizes rather than relying on Big-O alone for final performance decisions. Big-O is a tool for reasoning about scale, not a substitute for profiling.
© RM Full Stack & AI Engineer · All guides · Roadmaps · Open the app