O(2ⁿ)

—

Exponential Time

Danger

Every new item doubles the work. Avoid beyond tiny inputs.

Mental model

Like n light switches where each is ON or OFF. With 1 switch: 2 combos. 2 switches: 4. 3 switches: 8. Each extra switch doubles everything that already existed. n=30 → over a billion.

Interactive Visualisation

💡 Think of n light switches. Each switch is either ON or OFF — 2 states each. With n switches there are 2ⁿ possible combinations. Add one more switch and you instantly double every combination that already existed. n=20 → over a million. n=30 → over a billion.

n:→ 2³ = 8 subsets

IN/OUT

= 2³ = 8 combos

All 8 subsets:

Add 1 item → doubles every time

n=12

n=24

n=38

n=416

n=532

n=664

n=7128

n=8256

How it scales

n = 10

1,024 ops

n = 20

1,048,576 ops

n = 30

1,073,741,824 ops

n = 40

~1 trillion ops

O(n³) — Cubic Time

O(n!) — Factorial Time