Growth, not the number
Ask what happens when n doubles. The answer names the class: same, doubled, quadrupled, or one more step.
The gap widens
Two cost classes that look close at n of 10 can be millions apart at n of a million.
How work grows with size
The question that matters is not the count today but how the count grows when the input doubles. That growth is the cost class.
What you will see
10000000000
About 2 min of reading
Quick check
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Try It
Compare how four cost shapes grow.
1
Linear for 10, 20, 40.
def work(n):
s = 0
for i in range(n):
s += 1
return s
print([work(n) for n in (10, 20, 40)])
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[10, 20, 40]
2
Quadratic for 5, 10, 20.
def work(n):
s = 0
for i in range(n):
for j in range(n):
s += 1
return s
print([work(n) for n in (5, 10, 20)])
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[25, 100, 400]
3
Halving for 8, 16, 32.
def work(n):
s = 0
while n > 1:
n //= 2
s += 1
return s
print([work(n) for n in (8, 16, 32)])
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[3, 4, 5]
4
Squared of 100000.
n = 100000
print(n * n)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
10000000000
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
Cost is judged by growth as n doubles: constant stays, linear doubles, quadratic quadruples, logarithmic adds one step.
1
write cost in n
↓
2
double the input
↓
3
watch the new cost
↓
4
name the class
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.
def work(n):
sets nothing on screen
s = 0
sets nothing on screen
for i in range(n):
sets nothing on screen
s += 1
sets nothing on screen
return s
sets nothing on screen
print([work(n) for n in (10, 20, 40)])
[10, 20, 40]
Why this works
Examples
Double the input
def work(n):
s = 0
for i in range(n):
s += 1
return s
print([work(n) for n in (10, 20, 40)])Double n and the work doubles. That is linear growth.
Square grows fast
def work(n):
s = 0
for i in range(n):
for j in range(n):
s += 1
return s
print([work(n) for n in (5, 10, 20)])Double n and the work quadruples. That is quadratic growth.
Halving shrinks
def work(n):
s = 0
while n > 1:
n //= 2
s += 1
return s
print([work(n) for n in (8, 16, 32)])Double n and the work grows by one. Halving each step is logarithmic growth.
Fixed cost stays put
def work(n):
return 1 + 1
print([work(n) for n in (1, 1000, 1000000)])The cost does not look at n at all. That is constant time.
A table of growth
n = 16
print(n, n * n, n // 2)For n of 16 the three shapes are 16, 256, and 8. The gap widens as n grows.
Small n hides nothing
n = 3
print(n, n * n)At n of 3 the difference is 3 versus 9. Tiny inputs make bad shapes look fine.
Big n is the risk
n = 100000
print(n * n)A hundred thousand squared is ten billion. That many steps takes minutes, not microseconds.
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.
← What counts as a step
Previous Lesson
What counts as a step