Mojo Algorithm Complexity
Algorithm complexity measures how the runtime or memory usage of a program grows as the input size grows. Knowing complexity lets you predict whether a solution handles 100 items or 10 million items without running it first. This knowledge drives every performance decision in Mojo — when to vectorize, when to tile, and when to choose a different algorithm entirely.
The Restaurant Analogy
Finding one name in a guest list of N people:
Approach 1: Read every name until you find it
1 person → 1 check
10 people → up to 10 checks
1000 people → up to 1000 checks
Growth: proportional to N → O(n)
Approach 2: List is sorted alphabetically — flip to middle,
go left or right, repeat
1 person → 1 check
10 people → up to 4 checks
1000 people → up to 10 checks
Growth: proportional to log(N) → O(log n)
O(log n) wins by a massive margin at scale.
Big-O Notation
Big-O describes the worst-case growth rate of an algorithm, ignoring constant factors and lower-order terms. It answers: "as N doubles, how does the time change?"
Notation | Name | N=10 | N=100 | N=1000 ----------|---------------|-------|--------|-------- O(1) | Constant | 1 | 1 | 1 O(log n) | Logarithmic | 3 | 7 | 10 O(n) | Linear | 10 | 100 | 1000 O(n log n)| Log-linear | 33 | 664 | 9966 O(n²) | Quadratic | 100 | 10000 | 1000000 O(2^n) | Exponential |1024 | huge | ∞ (impractical)
Growth rate visual (relative time): O(1) ──────────────────────────── flat line O(log n) ─────────────────╱─ slow curve O(n) ──────────────╱──── diagonal O(n log n)────────────╱───── steeper diagonal O(n²) ──────────╱──────── steep curve O(2^n) ────────╱────────── vertical wall N → 10 100 1000 10000
O(1) — Constant Time
The operation takes the same time regardless of input size.
fn get_first(data: List[Int]) -> Int:
return data[0] # always one step, N doesn't matter
fn main():
var big = List[Int]()
for i in range(1000000):
big.append(i)
print(get_first(big)) # instant — O(1)
Examples of O(1): Array index access: data[i] Dictionary lookup: scores["Alice"] Stack push/pop: stack.push(x) Math operations: a + b, a * b
O(n) — Linear Time
Time grows proportionally with input size. Doubling N doubles the time.
fn find_max(data: List[Int]) -> Int:
var maximum = data[0]
for i in range(len(data)): # visits every element once
if data[i] > maximum:
maximum = data[i]
return maximum
Examples of O(n): Linear search (unsorted list) Summing all elements Printing every item Copying a list
O(n²) — Quadratic Time
A nested loop where both loops run N times. Doubling N quadruples the time.
fn bubble_sort(inout arr: List[Int]):
var n = len(arr)
for i in range(n): # outer loop: n times
for j in range(n - 1): # inner loop: n times
if arr[j] > arr[j+1]:
var t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t
Examples of O(n²): Bubble sort, selection sort, insertion sort (worst case) All-pairs comparison (find duplicates by brute force) Naive string search (fixed approach) N=100: 10,000 operations → fast N=10000: 100,000,000 ops → noticeable N=100000: 10 billion ops → too slow
O(log n) — Logarithmic Time
Each step halves the remaining work. Even for a billion items, only 30 steps are needed.
fn binary_search(data: List[Int], target: Int) -> Int:
var lo = 0
var hi = len(data) - 1
while lo <= hi:
var mid = (lo + hi) // 2
if data[mid] == target: return mid
elif data[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
Binary search halving diagram: N=1024 items: Step 1: 1024 → 512 (check middle, go left or right) Step 2: 512 → 256 Step 3: 256 → 128 Step 4: 128 → 64 Step 5: 64 → 32 ... Step 10: 1 → found or not found log₂(1024) = 10 steps max. log₂(1,000,000) ≈ 20 steps. log₂(1,000,000,000) ≈ 30 steps.
O(n log n) — Log-Linear Time
The best achievable complexity for comparison-based sorting. Merge sort and Mojo's built-in sort achieve this.
from algorithm import sort
fn main():
var data = List[Int]()
for i in range(100_000):
data.append(100_000 - i)
sort(data) # O(n log n) — handles 100k elements comfortably
print(data[0], data[len(data)-1]) # 1 100000
Space Complexity
Space complexity measures how memory usage grows with input size, using the same Big-O notation.
fn sum_list(data: List[Int]) -> Int:
var total = 0 # O(1) extra space — one variable
for i in range(len(data)):
total += data[i]
return total
fn copy_list(data: List[Int]) -> List[Int]:
var result = List[Int]() # O(n) extra space — grows with input
for i in range(len(data)):
result.append(data[i])
return result
Space complexity examples: O(1): bubble sort (sorts in-place, one temp variable) O(n): merge sort (needs a copy of the data) O(n): storing all elements in a new list O(n²): storing an n×n matrix
Measuring Complexity in Mojo Code
How to identify the complexity of your code:
Single loop over n items → O(n)
Two independent loops over n → O(n) + O(n) = O(n)
Loop inside a loop, both size n → O(n²)
Halving the input each step → O(log n)
Recursion that branches twice → O(2^n) — dangerous!
Recursion that halves each time → O(log n)
Example analysis:
fn example(data: List[Int]) -> Int:
var total = 0 # O(1)
for i in range(len(data)): # O(n)
for j in range(len(data)): # O(n) per outer step
total += data[i] * data[j]
return total
Overall: O(n × n) = O(n²)
Practical Impact in Mojo
Problem: process 1,000,000 data points Target: complete in under 1 second (CPU ~10⁹ ops/sec) Algorithm Complexity Operations Feasible? ───────────────────────────────────────────────── Direct access O(1) 1 Yes (instant) Linear scan O(n) 1,000,000 Yes Merge sort O(n log n) 20,000,000 Yes Bubble sort O(n²) 1,000,000,000,000 No (1000 seconds) Brute force O(2^n) ∞ No SIMD vectorization multiplies throughput by 8-16× but does NOT change the Big-O complexity class. O(n) with SIMD is still O(n), just ~10× faster in practice.
Key Takeaways
Big-O notation describes how algorithm runtime grows as input size N grows. O(1) is constant, O(log n) is logarithmic (binary search), O(n) is linear, O(n log n) is optimal sorting, O(n²) is quadratic (nested loops), and O(2^n) is exponential (impractical). Always check the complexity of your algorithm before optimizing at the hardware level — a faster CPU cannot save an O(n²) algorithm when n is large. SIMD and parallelism multiply throughput but do not change complexity class. Space complexity measures memory growth using the same notation. When choosing between algorithms, prefer the lower complexity class first, then optimize constants with Mojo's hardware features.