Big-O describes how an algorithm's running time or memory grows as the input size n grows. It captures the worst-case asymptotic behavior, ignoring constants and lower-order terms.
We care about growth rate, not exact step counts. O(2n + 5) is simply O(n) because as n grows large, constants and smaller terms stop mattering.
| Big-O | Name | Example |
|---|
| O(1) | constant | array index lookup |
| O(log n) | logarithmic | binary search |
| O(n) | linear | scanning a list |
| O(n log n) | linearithmic | merge sort |
| O(n²) | quadratic | nested loops |
| O(2ⁿ) | exponential | naive subsets |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O hides constants: an O(n) algorithm with a huge constant can lose to O(n log n) on small inputs. Also track space complexity, not just time.
Big-O lets you compare algorithms without running them or worrying about hardware.
It predicts which solutions survive when inputs grow from hundreds to millions — the difference between a feature that scales and one that times out.
It is the vocabulary every engineer uses to reason about performance.