Big O Notation

Definition

Big O notation is a mathematical notation used in computer science to describe how an algorithm's running time or memory usage grows as the size of its input increases, focusing on worst-case or upper-bound growth rate rather than exact timing.

Overview

Big O abstracts away hardware speed, constant factors, and implementation details to answer a specific question: as input size n grows very large, how does the algorithm's resource usage scale? Common classes include O(1) constant time, O(log n) logarithmic (as in binary search), O(n) linear, O(n log n) (as in efficient sorting algorithms like mergesort), O(n²) quadratic (as in simple nested-loop algorithms), and O(2^n) exponential — each describing a fundamentally different growth curve as inputs scale, which becomes the dominant factor in performance for sufficiently large inputs regardless of constant-factor optimizations. Big O is central to comparing data structures and algorithms: choosing a hash table over a linked list for lookups, for example, is fundamentally a Big O decision — O(1) average-case lookup versus O(n) linear search. It's also essential for reasoning about recursion's cost, since many recursive algorithms' complexity is derived from a recurrence relation describing how the problem shrinks with each call. Big O describes asymptotic, worst-case (or sometimes average-case) behavior, not actual wall-clock speed for any specific input size — an O(n²) algorithm can outperform an O(n log n) one on small inputs due to lower constant overhead. Related notations, Big Omega (best case) and Big Theta (tight bound), are less commonly used in everyday practice, but Big O itself is a standard part of technical interviews and a foundational tool for reasoning about algorithm scalability.

Key Concepts

• Describes how running time/memory scales with input size
• Focuses on asymptotic, worst-case growth rather than exact timing
• Common classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n)
• Ignores constant factors and hardware-specific speed differences
• Essential for comparing algorithms and data structures
• Standard framework used in technical coding interviews

Use Cases

Frequently Asked Questions

Related in Programming