One term wins
As n grows, the fastest growing term dominates. The others become a rounding error.
A class is a promise
Naming the class is a claim about large inputs. It is the claim you plan and review against.
Naming a cost class
A cost class keeps the term that grows fastest and drops the constants. That single name carries the plan for the whole program.
What you will see
11
About 2 min of reading
Try It
Reduce a total cost to its class.
1
Loop plus 500 for n of 10.
n = 10
steps = 0
for i in range(n):
steps += 1
steps += 500
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
510
2
n plus n squared for n of 6.
n = 6
steps = 0
for i in range(n):
steps += 1
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
42
3
Two per inner turn for n of 5.
n = 5
steps = 0
for i in range(n):
for j in range(n):
steps += 2
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
50
4
Halving then full loop for n of 8.
n = 8
steps = 0
k = n
while k > 1:
k //= 2
steps += 1
for i 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
11
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 cost class keeps the fastest growing term and drops constants. n plus n squared is called n squared.
1
total the cost
↓
2
find the fastest term
↓
3
drop constants
↓
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.
n = 10
sets nothing on screen
steps = 0
sets nothing on screen
for i in range(n):
sets nothing on screen
steps += 1
sets nothing on screen
steps += 500
sets nothing on screen
print(steps)
510
Why this works
Examples
Drop the constant
n = 10
steps = 0
for i in range(n):
steps += 1
steps += 500
print(steps)The loop plus 500 extra steps is n plus 500. For large n the loop is what matters.
Keep the fastest term
n = 6
steps = 0
for i in range(n):
steps += 1
for i in range(n):
for j in range(n):
steps += 1
print(steps)n plus n squared. The n squared term grows far faster, so it names the class.
Constants inside multiply
n = 5
steps = 0
for i in range(n):
for j in range(n):
steps += 2
print(steps)Two steps per inner turn is 2 n squared. The two is dropped, the class is n squared.
Log plus linear
n = 8
steps = 0
k = n
while k > 1:
k //= 2
steps += 1
for i in range(n):
steps += 1
print(steps)log n plus n. The linear part grows faster, so the class is linear.
n log n together
n = 8
steps = 0
for i in range(n):
k = n
while k > 1:
k //= 2
steps += 1
print(steps)A halving loop inside a full loop is n times log n. Neither part can be dropped.
Order of classes
print(1, 10, 33, 100, 10000)For n of 100 the classes are about 1, log n near 7, n log n near 700, n, and n squared at 10000.
The name sets the plan
n = 100000
print(n, n * n)A hundred thousand linear is fine, a hundred thousand squared is not. The name decides if the code ships.
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.
← Best, worst, and average
Previous Lesson
Best, worst, and average