Cases are different claims
Best case, worst case, and average case are three separate statements. Naming one is not claiming another.
Plan against the worst
Design uses the worst case. A fast average can still hide a slow input that matters.
Best, worst, and average
The same algorithm can cost different amounts depending on the input. Naming which case you mean keeps the claim honest.
What you will see
2
About 2 min of reading
Try It
Name the best, worst, and average case of a scan.
1
Target first.
a = [7, 2, 5]
target = 7
steps = 0
for x in a:
steps += 1
if x == target:
break
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
1
2
Target last.
a = [7, 2, 5]
target = 5
steps = 0
for x in a:
steps += 1
if x == target:
break
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
3
3
Sorted pass, no swaps.
a = [1, 2, 3]
swaps = 0
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
swaps += 1
print(swaps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
0
4
Reverse needs swaps.
a = [3, 2, 1]
swaps = 0
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
swaps += 1
print(swaps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
2
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
The same code can cost differently by input. Best, worst, and average are three separate claims, and design uses the worst.
1
pick an input
↓
2
measure best and worst
↓
3
estimate the average
↓
4
plan against the worst
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.
a = [7, 2, 5]
sets nothing on screen
target = 7
sets nothing on screen
steps = 0
sets nothing on screen
for x in a:
sets nothing on screen
steps += 1
sets nothing on screen
if x == target:
sets nothing on screen
break
sets nothing on screen
print(steps)
1
Why this works
Examples
Best case is early
a = [7, 2, 5]
target = 7
steps = 0
for x in a:
steps += 1
if x == target:
break
print(steps)The target is first, so the scan stops after one step. That is the best case.
Worst case is last
a = [7, 2, 5]
target = 5
steps = 0
for x in a:
steps += 1
if x == target:
break
print(steps)The target is last, so the scan uses all n steps. That is the worst case.
Already sorted is best
a = [1, 2, 3]
swaps = 0
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
swaps += 1
print(swaps)A pass over sorted data makes no swaps. Bubble sort best case is one pass.
Reverse is worst
a = [3, 2, 1]
swaps = 0
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
swaps += 1
print(swaps)Reversed data needs the most swaps. That is the worst case for the same code.
Average is a guess
a = [4, 1, 3, 2]
target = 3
steps = 0
for x in a:
steps += 1
if x == target:
break
print(steps)A random target sits in the middle on average, so about n over two steps. Same class as n.
Say which case
print("best 1, worst n, average n over 2")A claim without a case is vague. Best, worst, and average are different promises.
Worst case drives design
n = 1000
print("worst", n, "best", 1)Systems are planned against the worst case. A lucky best case is not a plan.
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.
← Halving the work
Previous Lesson
Halving the work