Imagine two delivery apps. Both show you the nearest restaurant — but one takes 2 seconds, the other takes 20. They both "work," but only one is usable at scale. This is what complexity analysis is all about: not just does it work, but how well does it scale?
What is Time Complexity?
Time complexity describes how the number of operations your algorithm performs grows as the input size (n) increases. It is not measuring actual clock time — it's measuring the growth rate of work done.
We express time complexity using Big O notation — a mathematical way to describe the upper bound (worst-case scenario) of an algorithm's performance.
Why worst-case? Because we need guarantees. If your app is slow for even a few users, that's a problem. Big O tells you how bad things can get.
Common Time Complexities with Examples
1. O(1) — Constant Time
The algorithm always does the same number of operations, no matter how large the input is.
def get_first(arr):
return arr[0] # O(1)
def get_value(d, key):
return d[key] # O(1)2. O(log n) — Logarithmic Time
The algorithm halves the problem with each step. Classic example: 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
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# For n = 1,000,000 elements → only ~20 comparisons needed!3. O(n) — Linear Time
The algorithm visits every element once. If input doubles, work doubles.
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val4. O(n log n) — Linearithmic Time
This is the complexity of most efficient sorting algorithms like Merge Sort and Quick 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
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
return result + left[i:] + right[j:]5. O(n²) — Quadratic Time
A loop inside a loop. If input doubles, work quadruples. Classic example: Bubble Sort.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arrAvoid O(n²) for large datasets. An array of 10,000 elements with an O(n²) algorithm does 100 million operations — what O(n log n) does in roughly 130,000.
6. O(2ⁿ) — Exponential Time
Each step doubles the work. Usually seen in recursive brute-force solutions.
# BAD: Exponential
def fib_bad(n):
if n <= 1:
return n
return fib_bad(n - 1) + fib_bad(n - 2) # O(2ⁿ)
# GOOD: Memoized — O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_good(n):
if n <= 1:
return n
return fib_good(n - 1) + fib_good(n - 2)Growth Rate Comparison (Visual)
For n = 100 elements, here's how many operations each complexity requires:
Big O Cheat Sheet
| Notation | Name | Example | Rating |
|---|---|---|---|
O(1) | Constant | Array index access, dict lookup | Excellent |
O(log n) | Logarithmic | Binary search, BST operations | Great |
O(n) | Linear | Linear search, single loop | Fair |
O(n log n) | Linearithmic | Merge sort, quicksort, heapsort | Acceptable |
O(n²) | Quadratic | Bubble sort, nested loops | Bad |
O(2ⁿ) | Exponential | Naive recursion, subset generation | Terrible |
O(n!) | Factorial | Permutation brute-force | Avoid |
What is Space Complexity?
Space complexity measures how much extra memory your algorithm uses relative to the input size. This includes variables, call stacks (for recursion), and any additional data structures you create.
It does not usually count the input itself — only the auxiliary space (extra memory on top of the input).
Time Complexity
Measures how many operations grow with input size n. Focused on CPU cycles and computation speed.
Space Complexity
Measures how much extra memory is consumed as n grows. Focused on RAM usage and memory efficiency.
Space Complexity Examples
O(1) Space — Constant
def sum_array(arr):
total = 0
for num in arr:
total += num
return total
# Space: O(1)O(n) Space — Linear
def duplicate_array(arr):
result = []
for num in arr:
result.append(num)
return result
# Space: O(n)O(n) Space — Recursive Call Stack
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
# Space: O(n) due to call stack depthO(n²) Space — Quadratic
def create_matrix(n):
matrix = [[0] * n for _ in range(n)]
return matrix
# Space: O(n²)The Classic Trade-off: Time vs Space
# Approach 1: Brute Force
# Time: O(2ⁿ) | Space: O(n) call stack
def fib_brute(n):
if n <= 1: return n
return fib_brute(n-1) + fib_brute(n-2)
# Approach 2: Memoization (trade space for time)
# Time: O(n) | Space: O(n)
memo = {}
def fib_memo(n):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
# Approach 3: Bottom-up DP (optimal)
# Time: O(n) | Space: O(1)
def fib_dp(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bThe bottom-up DP approach is the winner — O(n) time and O(1) space. Always try to find the approach that avoids unnecessary memory use without sacrificing speed.
How to Analyze an Algorithm Step-by-Step
- Drop constants: O(2n) → O(n)
- Drop lower-order terms: O(n² + n) → O(n²)
- Sequential steps add: O(n) + O(n²) = O(n²)
- Nested loops multiply: A loop of n inside a loop of n = O(n²)
- Halving per step = log: If you halve the input each step, it's O(log n)
def example(arr):
for x in arr: # O(n)
print(x)
for i in arr: # O(n²) — nested
for j in arr:
print(i, j)
# Total: O(n) + O(n²) → O(n²)Quick Summary
| Concept | What it measures | Unit | Goal |
|---|---|---|---|
| Time Complexity | Operations as n grows | Operations / Steps | As small as possible |
| Space Complexity | Extra memory as n grows | Memory (bytes) | As small as possible |
| Big O Notation | Worst-case upper bound | O(…) | Understand the worst scenario |
Practice challenge: Given this code — for i in range(n): for j in range(i, n): print(i, j) — what is the time complexity? (Answer: O(n²), since the total iterations ≈ n(n+1)/2 which simplifies to O(n²).)
Understanding Big O is foundational to writing scalable software, cracking DSA interview questions, and making smart engineering decisions. Practice by analyzing every function you write — ask yourself: what's the time complexity? What's the space complexity? That habit alone will make you a better developer.