Big O notation is a way to describe how fast an algorithm runs (or how much memory it uses) as the input size grows. It gives us a common language to compare algorithms without actually running them.
In simple language, Big O answers: “If we double the input, how much slower does this get?”
We don’t care about exact milliseconds. We care about the growth rate. An O(n) algorithm might be slower than O(n²) for 5 items, but for a million items? O(n) wins every time.
Common Complexity Classes
Here’s the lineup from fastest to slowest:
| Big O | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Single loop through array |
| O(n log n) | Linearithmic | Merge sort, quick sort |
| O(n²) | Quadratic | Nested loops |
| O(2^n) | Exponential | Recursive fibonacci (naive) |
Visual Comparison
Look at that jump from O(n²) to O(2^n). That’s why complexity matters — a bad algorithm can turn a one-second task into a “heat death of the universe” situation.
How to Analyze Code
The key rules are simple:
- Drop constants — O(2n) is just O(n)
- Drop smaller terms — O(n² + n) is just O(n²)
- Loops — a single loop over n items is O(n)
- Nested loops — a loop inside a loop is O(n × m), or O(n²) if both go over the same array
- Halving — if we cut the problem in half each step, that’s O(log n)
O(1) — Constant Time
No matter how big the input is, we do the same amount of work.
// Accessing an array element by index -- always instant
function getFirst(arr) {
return arr[0]; // one operation, regardless of array size
}# Accessing a list element by index -- always instant
def get_first(arr):
return arr[0] # one operation, regardless of list size// Accessing an array element by index -- always instant
static int getFirst(int[] arr) {
return arr[0]; // one operation, regardless of array size
}O(log n) — Logarithmic
We cut the input in half each step. Binary search is the classic example.
// Binary search -- halves the search space each iteration
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}# Binary search -- halves the search space each iteration
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1// Binary search -- halves the search space each iteration
static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}For an array of 1 billion elements, binary search needs at most ~30 steps. That’s the power of O(log n).
O(n) — Linear
We touch each element once. Double the input, double the work.
// Find the maximum -- must check every element
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}# Find the maximum -- must check every element
def find_max(arr):
max_val = arr[0]
for num in arr[1:]:
if num > max_val:
max_val = num
return max_val// Find the maximum -- must check every element
static int findMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}O(n²) — Quadratic
Nested loops where both iterate over the input. This is where things start getting slow.
// Check for duplicates with brute force -- every pair gets compared
function hasDuplicate(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true;
}
}
return false;
}# Check for duplicates with brute force -- every pair gets compared
def has_duplicate(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False// Check for duplicates with brute force -- every pair gets compared
static boolean hasDuplicate(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) return true;
}
}
return false;
}For 10,000 elements, that’s ~50 million comparisons. For 100,000 elements, it’s ~5 billion. Yikes.
O(2^n) — Exponential
Each step doubles the work. Recursive fibonacci without memoization is the classic example.
// Naive fibonacci -- each call spawns TWO more calls
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // two recursive calls = exponential
}# Naive fibonacci -- each call spawns TWO more calls
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2) # two recursive calls = exponential// Naive fibonacci -- each call spawns TWO more calls
static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // two recursive calls = exponential
}fib(40) makes over a billion function calls. fib(50) could take minutes. We’ll fix this later with dynamic programming.
Space Complexity
Time complexity measures how fast we are. Space complexity measures how much extra memory we use.
The rules are the same — we use Big O notation, but we count memory instead of operations.
// O(1) space -- we only use a few variables, no matter the input size
function sum(arr) {
let total = 0; // just one variable
for (const num of arr) {
total += num;
}
return total;
}
// O(n) space -- we create a new array the same size as the input
function doubled(arr) {
const result = []; // grows with input size
for (const num of arr) {
result.push(num * 2);
}
return result;
}# O(1) space -- we only use a few variables, no matter the input size
def sum_arr(arr):
total = 0 # just one variable
for num in arr:
total += num
return total
# O(n) space -- we create a new list the same size as the input
def doubled(arr):
result = [] # grows with input size
for num in arr:
result.append(num * 2)
return result// O(1) space -- we only use a few variables, no matter the input size
static int sum(int[] arr) {
int total = 0; // just one variable
for (int num : arr) {
total += num;
}
return total;
}
// O(n) space -- we create a new array the same size as the input
static int[] doubled(int[] arr) {
int[] result = new int[arr.length]; // grows with input size
for (int i = 0; i < arr.length; i++) {
result[i] = arr[i] * 2;
}
return result;
}In interviews, always mention both time and space complexity. A common trade-off is using extra memory (like a hash map) to make the algorithm faster. That’s the classic time-space trade-off.