Nesting multiplies
Each extra loop over n multiplies the cost by n. Two loops give n squared, three give n cubed.
A set buys a step
Replacing a list with a set turns a scan into one lookup, which can remove a whole factor of n.
Nested loops multiply
A loop inside a loop multiplies the work. That is the shape to look for, and the shape to avoid when n can grow.
What you will see
8
About 2 min of reading
Try It
Measure nested loops and remove one factor.
1
Full grid of 4.
n = 4
steps = 0
for i in range(n):
for j in range(n):
steps += 1
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
16
2
Triangle of 4.
n = 4
steps = 0
for i in range(n):
for j in range(i, n):
steps += 1
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
10
3
Cube of 3.
n = 3
steps = 0
for i in range(n):
for j in range(n):
for k in range(n):
steps += 1
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
27
4
Set membership loop.
a = [1, 2, 3, 4]
s = set(a)
steps = 0
for x in a:
steps += 1
if x in s:
steps += 1
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
8
Put it in order
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Data Flow
A loop inside a loop multiplies the cost by n. Triangular loops are still quadratic, and a set can remove one factor.
1
find the nesting
↓
2
multiply the loop counts
↓
3
check the hidden scans
↓
4
trade a set for a scan
Line by line
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
n = 4
sets nothing on screen
steps = 0
sets nothing on screen
for i in range(n):
sets nothing on screen
for j in range(n):
sets nothing on screen
steps += 1
sets nothing on screen
print(steps)
16
Why this works
Examples
Full grid
n = 4
steps = 0
for i in range(n):
for j in range(n):
steps += 1
print(steps)n outer turns times n inner turns is n squared. For 4 that is 16.
Triangle is still quadratic
n = 4
steps = 0
for i in range(n):
for j in range(i, n):
steps += 1
print(steps)The inner loop shrinks but the total is about n squared over two. Same class.
Three deep is cubed
n = 3
steps = 0
for i in range(n):
for j in range(n):
for k in range(n):
steps += 1
print(steps)Three nested loops of n cost n cubed. For 3 that is 27.
A sort inside a loop
rows = [[3, 1], [4, 2], [9, 0]]
steps = 0
for r in rows:
r.sort()
steps += 1
print([len(r) for r in rows])Sorting inside a loop pays the sort cost every turn. The hidden loop still counts.
Membership in a list
a = [1, 2, 3, 4]
steps = 0
for x in a:
steps += 1
if x in a:
steps += 1
print(steps)Checking membership in a list scans it. Inside a loop that is quadratic.
Swap for a set
a = [1, 2, 3, 4]
s = set(a)
steps = 0
for x in a:
steps += 1
if x in s:
steps += 1
print(steps)Membership in a set is one step on average, so the loop stays linear.
Quadratic is a limit
n = 2000
print(n * n)Two thousand squared is four million steps. That is fine. At fifty thousand it is not.
Words this lesson uses
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← Constant and linear work
Previous Lesson
Constant and linear work