O(n³)
—Cubic Time
CautionThree nested loops. Only for very small inputs.
Mental model
Three loops ticking together — for every i, for every j, for every k. The classic example: naive matrix multiplication. n=10 seems fine at 1,000 ops. n=100 silently becomes 1 million.
Interactive Visualisation
🎲 Three nested loops — for every i, for every j, for every k. Classic example: naive matrix multiplication. Even n=10 means 1,000 operations. n=100 hits a million. It looks fine until it suddenly isn't.
n:→ 3³ = 27 ops
i= 0
0
1
2
j= 0
0
1
2
k= 0
0
1
2
for i in range(3): # 3 times
for j in range(3): # 3 times
for k in range(3): # 3 times
work(i=0, j=0, k=0)
n³ grows even faster
n=28
n=327
n=5125
n=101k
n=50125k
n=1001M
How it scales
n = 5
125 ops
n = 10
1,000 ops
n = 50
125,000 ops
n = 100
1,000,000 ops