Algorithm Complexity & Big O Notation

Chapter 13

FREE Big O Notation — Measuring Algorithm Efficiency

Article · 18 min

How do we compare algorithms? We use Big O notation — a way to describe how an algorithm's runtime grows as the input size grows.

Common Big O Runtimes

Notation	Name	Example	n=1000
O(1)	Constant	Array access by index	1 step
O(log n)	Logarithmic	Binary search	~10 steps
O(n)	Linear	Linear search	1000 steps
O(n log n)	Linearithmic	Merge sort	~9966 steps
O(n²)	Quadratic	Bubble sort	1,000,000 steps
O(2ⁿ)	Exponential	Fibonacci recursive	Impossible!

Practice 1

What is the Big O of accessing any element in a Python list by index?
What is the Big O of finding an element in a Python dictionary by key?
If algorithm A takes O(n) and algorithm B takes O(n²), which is faster for large inputs?

Determining Big O

Rules of thumb:

A single operation → O(1)
A loop over n items → O(n)
A loop that halves the input each time → O(log n)
Nested loops → multiply: O(n × m)
Drop constants: O(2n) → O(n)
Keep the dominant term: O(n² + n) → O(n²)

# O(n) — single loop
for i in range(n):
    print(i)

# O(n²) — nested loop
for i in range(n):
    for j in range(n):
        print(i, j)

# O(n²) — even with constant factor
for i in range(n):
    for j in range(100):    # 100 is constant!
        print(i, j)

Practice 2

What is the Big O of this code?

for i in range(n):
    for j in range(i):
        print(i, j)

What is the space complexity of an in-place bubble sort?