Basic

Counting the work

Before you run code, you can count how much work it does. The count is what decides whether a program finishes in a blink or in an hour.

What you will see

[1, 2, 4, 8]

About 2 min of reading

Try It

Count the steps of small loops by hand.

Count one loop of 5.

n = 5 count = 0 for i in range(n): count += 1 print(count)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Two loops of 4 each.

n = 4 steps = 0 for i in range(n): steps += 1 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

Nested loops of 4.

n = 4 steps = 0 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

Counts for 1, 2, 4, 8.

def count(n): s = 0 for i in range(n): s += 1 return s print([count(k) for k in (1, 2, 4, 8)])

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[1, 2, 4, 8]

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

Work is counted in steps, expressed as a function of the input size n. Separate loops add, nested loops multiply.

1 pick the input size n

↓

2 count the loop body turns

↓

3 add separate loops

↓

4 multiply nested loops

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 = 5 sets nothing on screen

count = 0 sets nothing on screen

for i in range(n): sets nothing on screen

count += 1 sets nothing on screen

print(count) 5

Why this works

Count before you run

Counting the steps of an algorithm tells you the shape of the cost. That shape survives a faster machine or a slower one.

Input size is the variable

Every count is written in terms of n, the size of the input. The number alone means nothing without n.

Examples

Count with a counter

n = 5
count = 0
for i in range(n):
    count += 1
print(count)

The counter ends at n. The loop body ran exactly n times.

Two loops, two counts

n = 4
steps = 0
for i in range(n):
    steps += 1
for j in range(n):
    steps += 1
print(steps)

Two separate loops cost n plus n. They do not multiply.

Nested loops multiply

n = 4
steps = 0
for i in range(n):
    for j in range(n):
        steps += 1
print(steps)

The inner loop runs n times for each of n outer turns. That is n times n.

Work is not time

n = 1000
steps = 0
for i in range(n):
    steps += 1
print(steps)

The count is work, not seconds. A step here could be one add or a disk read.

Size drives the count

def count(n):
    s = 0
    for i in range(n):
        s += 1
    return s
print([count(k) for k in (1, 2, 4, 8)])

The count is a function of the input size. Doubling the input doubles the work.

Ignore the print

n = 6
steps = 0
for i in range(n):
    steps += 1
print(steps)

One extra step at the end does not change the shape. The loop still dominates.

A counter you can read

n = 3
steps = 0
for i in range(n):
    steps += 1
    print(steps)

The counter prints 1, 2, 3. Each turn adds one step.

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.

Next Lesson

What counts as a step

What counts as a step →