A step is a model
You choose what counts as one step. The choice must be honest, but the shape of the answer barely changes.
Library calls hide loops
A one line call like sort or sum is not free. Its cost is part of your count.
What counts as a step
A step is one unit of work the machine does: a comparison, an add, an assignment, a lookup. Counting steps is a model, and the model only needs to be honest.
What you will see
5
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
Count steps for lines that hide work.
1
Compare until found.
a = [3, 1, 2]
target = 2
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
2
Copy a list of 3.
a = [1, 2, 3]
b = a[:]
print(len(b))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
3
3
All pairs of 3.
a = [4, 2, 1]
steps = 0
for i in range(len(a)):
for j in range(i + 1, len(a)):
steps += 1
print(steps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
3
4
Append 5 items.
n = 5
a = []
for i in range(n):
a.append(i)
print(len(a))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
5
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 step is one unit of work: compare, add, assign, or lookup. Library calls like sort or sum hide loops that still cost work.
1
name the unit of work
↓
2
count compares and lookups
↓
3
open the hidden loops
↓
4
cost in n
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 = [3, 1, 2]
sets nothing on screen
target = 2
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)
3
Why this works
Examples
A comparison is a step
a = [3, 1, 2]
target = 2
steps = 0
for x in a:
steps += 1
if x == target:
break
print(steps)Each turn does a compare. The count stops early because the loop breaks.
A lookup is a step
d = {"a": 1, "b": 2}
steps = 0
steps += 1
v = d["b"]
print(v, steps)Reading a key from a dict is one step on average. The count does not scan the dict.
Copying is not free
a = [1, 2, 3]
b = a[:]
print(len(b))Slicing copies every element, so it costs n steps. A cheap looking line can hide a loop.
Sorting hides a cost
a = [5, 3, 1, 4]
a.sort()
print(a)The sort is one line but it does n log n work inside. A library call still has a cost.
Build the list
n = 5
a = []
for i in range(n):
a.append(i)
print(a)Append is one step per call on average, so building costs n steps total.
Sum is a loop inside
a = [1, 2, 3, 4]
print(sum(a))sum walks the whole list, so it costs n steps even though it looks like one word.
Count the compares
a = [4, 2, 1]
steps = 0
for i in range(len(a)):
for j in range(i + 1, len(a)):
steps += 1
print(steps)All pairs of three items is three compares. The inner loop starts at i plus 1.
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.
← Counting the work
Previous Lesson
Counting the work