Constant means no n
Constant time does not read the input size. The cost is the same for ten items and ten million.
Linear means one pass
Linear work touches each item a constant number of times. Two passes or half the items are still linear.
Constant and linear work
Some work does not depend on the input at all, and some work touches every item once. Both are cheap, and both are worth naming.
What you will see
6 3
About 2 min of reading
Try It
Tell constant work from linear work.
1
First item of a list.
a = [9, 8, 7]
print(a[0])
Before you run it, say out loud what it will print. Then open the answer.
What it prints
9
2
Pairs formula for 1000000.
n = 1000000
print(n * (n - 1) // 2)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
499999500000
3
Largest of four.
a = [5, 3, 9, 1]
best = a[0]
for x in a:
if x > best:
best = x
print(best)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
9
4
Two passes over three.
a = [1, 2, 3]
s = 0
for x in a:
s += x
m = 0
for x in a:
m = max(m, x)
print(s, m)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
6 3
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
Constant work ignores n. Linear work touches every item a constant number of times, so two passes are still linear.
1
ask if n is read
↓
2
one step or one pass
↓
3
count the passes
↓
4
name constant or linear
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 = [9, 8, 7]
sets nothing on screen
print(a[0])
9
Why this works
Examples
Constant time
a = [9, 8, 7]
print(a[0])Reading the first item costs one step whatever the length of the list.
Constant with a formula
n = 1000000
print(n * (n - 1) // 2)The formula for a sum of pairs is a few steps, no loop. That is constant time.
Linear scan
a = [5, 3, 9, 1]
best = a[0]
for x in a:
if x > best:
best = x
print(best)Finding the largest touches every item once. That is linear.
Linear is a floor for scanning
a = [4, 7, 2]
found = False
for x in a:
if x == 7:
found = True
print(found)An unsorted list can hide the answer last, so a scan may need all n items.
Two passes are still linear
a = [1, 2, 3]
s = 0
for x in a:
s += x
m = 0
for x in a:
m = max(m, x)
print(s, m)Two full passes cost 2n. That is the same class as n.
Half is still linear
a = [1, 2, 3, 4]
c = 0
for x in a:
if x % 2 == 0:
c += 1
print(c)The body runs on some items but the loop still visits all n. Linear.
Length is constant
a = list(range(5))
print(len(a))A list stores its length, so len is one step. It does not walk the items.
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.
← How work grows with size
Previous Lesson
How work grows with size