Big-O Notation
Big-O notation is the universal language for describing how an algorithm's resource consumption — time or memory — grows as the input size increases. It provides an abstract, hardware-independent way to compare algorithms and predict scalability.
This guide covers the formal definition of Big-O, common complexity classes (constant through factorial), asymptotic notation (O, Ω, Θ), amortized analysis, practical tips for analyzing code, code walkthroughs, and a 10-question practice quiz.
Complexity Growth Comparison
Growth Curves (log–log scale)
1Introduction
In the world of computer science, where every millisecond and byte counts, understanding how efficiently our code performs is paramount. It's not enough for a program to simply “work” — it must also perform well, especially as the amount of data it processes grows. Big-O notation is the mathematical tool that allows us to describe the performance or complexity of an algorithm.
Big-O helps us predict how an algorithm will behave as the input size (often denoted as n) increases, without needing to run it on specific hardware or with specific data. It underpins Algorithm Design, Data Structures, Systems Design, and virtually every technical interview in software engineering.
Choosing an O(n log n) sorting algorithm over an O(n²) one can mean the difference between a program that finishes in seconds and one that takes years on large datasets. Every database query planner, search engine, and real-time system relies on Big-O analysis to make critical design decisions.
2Key Definitions
Essential terms for understanding algorithmic complexity at the university level.
Big-O (O)
Upper bound on growth rate; describes worst-case scaling
Big-Omega (Ω)
Lower bound on growth rate; describes best-case scaling
Big-Theta (Θ)
Tight bound; growth rate is sandwiched between upper and lower bounds
Time Complexity
Growth rate of operations performed relative to input size
Space Complexity
Growth rate of memory used relative to input size
Asymptotic Analysis
Studying behavior as input size approaches infinity
Amortized Cost
Average cost per operation over a sequence of operations
Dominant Term
The fastest-growing term in an expression (e.g., n² in 3n² + 5n + 1)
Worst Case
Maximum resources required for any input of size n
Best Case
Minimum resources required for any input of size n
Average Case
Expected resources averaged over all possible inputs of size n
Time-Space Trade-off
Using more memory to reduce time, or vice versa
3Common Complexity Classes
From the fastest to the slowest, here are the most important complexity classes every CS student must know.
O(1) — Constant Time
The number of operations does not depend on input size. It takes the same time regardless of how large the input is.
- Array access by index:
arr[i] - Hash table insertion / lookup (average)
- Stack push / pop
Analogy: Finding a book by its exact call number on a shelf.
O(log n) — Logarithmic Time
The problem size is halved at each step. When n doubles, time increases by only a constant additive amount.
- Binary search on a sorted array
- Balanced BST lookup
- Exponentiation by squaring
Analogy: Looking up a word in a dictionary by narrowing down the section.
O(n) — Linear Time
The number of operations grows proportionally to input size. If the input doubles, the time approximately doubles.
- Linear search through an unsorted array
- Finding maximum / minimum element
- Iterating through a linked list
Analogy: Reading every page of a book.
O(n log n) — Linearithmic Time
Slightly worse than linear, but considered very efficient for large datasets. The gold standard for comparison-based sorting.
- Merge Sort, Heap Sort (all cases)
- Quick Sort (average case)
- Many divide-and-conquer algorithms
Analogy: Sorting cards by repeatedly splitting, sorting halves, and merging back.
O(n²) — Quadratic Time
Often caused by nested loops where each iterates n times. If n doubles, time quadruples.
- Bubble Sort, Selection Sort, Insertion Sort
- Checking all pairs in an array
- Naive matrix operations
Analogy: Comparing every person in a room to every other person.
O(2n) — Exponential Time
Operations double with each additional element. Impractical for anything beyond very small n.
- Naive recursive Fibonacci
- Brute-force subset generation
- Some backtracking problems without pruning
Analogy: Trying every combination to unlock a safe.
O(n!) — Factorial Time
The worst practical complexity. Even n=20 is too large for most systems.
- Generating all permutations of a set
- Brute-force Traveling Salesperson Problem
Analogy: Generating all possible seating arrangements for n dinner guests.
4Analyzing Code Complexity
Here are the practical rules for determining the Big-O of a piece of code.
Rule 1: Focus on Loops
A single loop over n items is O(n). Nested loops multiply: two nested loops over n are O(n²). A loop that halves the input each iteration is O(log n).
Rule 2: Drop Constants and Lower-Order Terms
O(3n² + 5n + 100) simplifies to O(n²). Constants don't change the growth rate, and lower-order terms become negligible as n grows.
Rule 3: Sequential Steps Add, Nested Steps Multiply
An O(n) block followed by an O(n²) block is O(n + n²) = O(n²). An O(n) loop inside an O(m) loop is O(n × m).
Rule 4: Recursive Calls
Analyze the recursion tree: depth × work per level. A function calling itself twice with half the input (like Merge Sort) is O(n log n). A function calling itself twice with n−1 (like naive Fibonacci) is O(2n).
Rule 5: Data Structure Operations
Know the complexity of operations on your data structures: array access O(1), hash lookup O(1) average, sorted array binary search O(log n), linked list search O(n).
5Big-O vs Omega vs Theta
Big-O is only part of the asymptotic picture. To fully characterize an algorithm, you need all three notations.
Big-O (O)
Upper bound. “My algorithm will never be worse than this.”
f(n) ≤ c · g(n) for n ≥ n&sub0;
Omega (Ω)
Lower bound. “My algorithm will always take at least this long.”
f(n) ≥ c · g(n) for n ≥ n&sub0;
Theta (Θ)
Tight bound. “My algorithm is always this — best and worst case match.”
c&sub1; · g(n) ≤ f(n) ≤ c&sub2; · g(n)
Case Analysis Example: Linear Search
Best Case: Ω(1)
Target is the first element checked.
Average Case: O(n)
On average, you check half the array.
Worst Case: O(n)
Target is last or not found — must check every element.
Merge Sort is Θ(n log n) because its best, worst, and average cases all share the same growth rate. Linear search is O(n) and Ω(1) because the bounds differ — it is not Θ(n).
6Amortized Analysis
Sometimes a sequence of operations has a few very expensive ones mixed with many cheap ones. Amortized analysis averages the total cost across all operations, giving a more accurate picture than worst-case analysis for each individual operation.
Dynamic Array (ArrayList / Python list)
Most append() operations are O(1). But when the underlying array runs out of space, a new array with double the capacity is allocated and all elements are copied — an O(n) operation.
Because resizes happen at capacities 1, 2, 4, 8, 16, ..., the total cost of n appends is 1 + 1 + 1 + ... + (copies during resizes). The geometric series sums to approximately 3n, so the amortized cost per append is O(1).
Total for n appends: ~3n → Amortized per operation: O(1)
7Code Walkthroughs
O(1) — Constant Time: Array Access
def get_first_element(arr):
# Accessing an element by index is O(1)
if not arr:
return None
return arr[0]
my_list = [10, 20, 30, 40, 50]
print(get_first_element(my_list)) # 10Line 4: A single bounds check — constant time regardless of array length.
Line 5: Direct index access is one operation — the array calculates the memory address in O(1).
Key insight: The size of the array does not affect how long it takes to access a single element by index.
O(log n) — Logarithmic Time: Binary Search
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Found
elif arr[mid] < target:
low = mid + 1 # Discard left half
else:
high = mid - 1 # Discard right half
return -1 # Not found
sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(sorted_list, 23)) # 5Line 4: Each iteration of the while loop halves the search space.
Lines 8–11: We discard one half entirely — the problem size goes from n to n/2 to n/4 ...
Total iterations: log&sub2;(n) — for 1,000,000 elements, at most 20 comparisons.
Key insight: Every time you halve the problem, you get logarithmic complexity. This is why sorted data enables fast search.
O(n) — Linear Time: Find Maximum
def find_max(arr):
max_val = arr[0]
for x in arr:
if x > max_val:
max_val = x
return max_val
my_list = [1, 5, 2, 8, 3, 9, 4]
print(find_max(my_list)) # 9Line 3: The for loop visits every element exactly once — n iterations.
Line 4: A constant-time comparison inside the loop.
Total: n comparisons, so the function is O(n).
Key insight: To find the maximum, you must examine every element at least once — you cannot do better than O(n).
O(n²) — Quadratic Time: Bubble Sort
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
my_list = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(my_list))Line 3: Outer loop runs n times.
Line 4: Inner loop runs up to n−1 times for each outer iteration.
Total comparisons: n(n−1)/2 ≈ n²/2 → O(n²).
Key insight: Nested loops that both scale with n produce quadratic complexity — this is why Bubble Sort is inefficient for large datasets.
O(n log n) — Linearithmic Time: Merge Sort
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultLines 4–6: Array is split in half recursively — this creates log n levels of recursion.
Lines 11–15: Merging two halves takes O(n) work at each level.
Total: log n levels × O(n) work per level = O(n log n).
Key insight: Divide-and-conquer splits the problem (log n depth) and does linear work at each level, yielding the efficient O(n log n).
Amortized O(1) — Dynamic Array Append
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.array = [None] * self.capacity
def append(self, item):
if self.size == self.capacity:
self.capacity *= 2 # Double capacity
new_array = [None] * self.capacity
for i in range(self.size): # Copy O(n)
new_array[i] = self.array[i]
self.array = new_array
self.array[self.size] = item # O(1)
self.size += 1Line 8: Resize check — only triggers when the array is full.
Lines 9–13: Resize doubles capacity and copies all elements — O(n), but happens exponentially less often.
Line 14: Normal append is O(1) — just place the item.
Key insight: Doubling strategy ensures the expensive O(n) resize is spread across many O(1) appends, keeping the amortized cost constant.
8Memory Aids
“O(1) = knowing your locker combination. O(n) = trying every locker to find your stuff.”
“O(log n) = phone book search. Open to the middle, discard half, repeat.”
“O(n²) = handshake problem. If everyone in a room shakes hands with everyone else, the number of handshakes is n(n−1)/2.”
“Big-O is like asking 'is this trip cross-town or cross-country?' — the exact speed limit doesn't matter, the scale does.”
“Amortized O(1) is like paying monthly rent — one big annual payment spread across 12 months feels manageable.”
“O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2n) < O(n!) — memorize this ranking like the musical scale.”
9Common Mistakes
Saying “O(2n)” or “O(3n²)”
Constants are dropped in Big-O. O(2n) is just O(n). O(3n² + 5n) is O(n²). The constant multiplier does not change the growth rate.
“This O(n) algorithm takes n milliseconds ”
Big-O describes the growth rate of operations, not actual time. An O(n) algorithm might take 5n or 0.001n operations — Big-O abstracts away the constant factor and hardware specifics.
“This function is O(n) because it has one loop”
Built-in functions hide complexity. Python's list.sort() is O(n log n), in on a list is O(n), and string concatenation in a loop can be O(n²). Always account for the complexity of called functions.
“Big-O means worst case”
Big-O is an upper bound notation, not “worst case.” You can say the best-case of Insertion Sort is O(n) — that's an upper bound on the best case. Big-O, Ω, and Θ describe bounds; best/worst/average describe cases. They are independent concepts.
“Dynamic array append is O(n) because it sometimes resizes”
Amortized analysis is not the same as average-case analysis. Average case averages over all possible inputs. Amortized analysis averages over a sequence of operations on the same data structure, providing a guarantee — not a probabilistic expectation.
Saying two nested O(n) loops are O(n + n) = O(n)
Sequential (one after another) steps add: O(n) + O(n) = O(n). Nested (one inside another) steps multiply: O(n) × O(n) = O(n²). This distinction is critical.
“O(1) is always better than O(n)”
O(1) means constant, not fast. An O(1) operation that takes 10 seconds is slower than an O(n) operation on 5 elements taking 1ms each. Big-O matters for scaling behavior, not small inputs.
Only analyzing time and ignoring memory usage
Merge Sort is O(n log n) time but O(n) space. In memory-constrained environments, an in-place O(n²) algorithm like Insertion Sort might be preferable. Always analyze both dimensions.
Frequently Asked Questions
- What is Big-O notation and why does it matter?
- Big-O notation is a mathematical tool that describes the upper bound of an algorithm's growth rate relative to input size. It matters because it lets you predict how an algorithm will scale — an O(n²) algorithm that works fine for 100 items may take years for 1,000,000 items, while an O(n log n) algorithm handles it in seconds.
- What is the difference between Big-O, Omega, and Theta notation?
- Big-O (O) describes the upper bound (worst-case growth rate). Omega (Ω) describes the lower bound (best-case growth rate). Theta (Θ) describes the tight bound — when best and worst cases have the same growth rate. For example, Merge Sort is Θ(n log n) because all cases are n log n, while linear search is O(n) but Ω(1).
- Why do we drop constants and lower-order terms in Big-O?
- Big-O focuses on asymptotic behavior — what happens as n approaches infinity. At large scale, constants (like 3 in 3n²) and lower terms (like 5n in 3n² + 5n) become negligible compared to the dominant term. The growth rate is what determines scalability, not the constant multiplier.
- What is amortized analysis?
- Amortized analysis averages the cost of operations over a sequence. For example, appending to a dynamic array is usually O(1), but occasionally triggers an O(n) resize. Since resizes happen infrequently (capacity doubles each time), the amortized cost per append is still O(1). It spreads rare expensive operations across many cheap ones.
- How do I determine the Big-O of my code?
- Focus on loops (a single loop over n items is O(n), nested loops are O(n²)), recursive calls (each level of branching multiplies), and the data structures used (hash table lookup is O(1), sorted array search is O(log n)). Always identify the dominant term and drop constants and lower-order terms.
- What is the difference between time complexity and space complexity?
- Time complexity measures how the number of operations grows with input size. Space complexity measures how memory usage grows. They are analyzed independently using the same Big-O notation. Often there is a trade-off: using more memory (like a hash table) can reduce time complexity.
Practice Quiz
Test your understanding of Big-O notation — select the correct answer for each question.
1.Which Big-O notation represents an algorithm whose execution time does NOT increase with the input size?
2.What is the typical time complexity of Binary Search on a sorted array?
3.What does Big-O notation formally describe about an algorithm?
4.An algorithm with two nested loops, each iterating n times, most likely has which time complexity?
5.Which asymptotic notation represents a tight bound, meaning the algorithm is bounded both above and below by the same function?
6.Which sorting algorithm achieves O(n log n) in its best, worst, AND average cases?
7.What does Amortized Analysis primarily focus on?
8.What is the simplified Big-O of the expression 3n² + 5n + 100?
9.What is the time complexity of the naive recursive Fibonacci algorithm (without memoization)?
10.What does Omega (Ω) notation represent?
Study Tips
- Practice on real code: Take functions you have written and determine their Big-O. Start with the loops and work outward.
- Draw the recursion tree: For recursive algorithms, sketch the call tree to visualize depth (log n levels?) and branching factor (2 calls each?).
- Memorize the ranking: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2n) < O(n!). Know it cold for exams and interviews.
- Use comparison tables: Plug in n = 10, 100, 1000 to see how quickly different complexities diverge.