DailyRNG

Advanced

Reading real costs

The class predicts the shape, but real inputs and real machines set the constant. Measure to confirm the model, not to replace it.

What you will see

1000

About 2 min of reading

Try It

Confirm a cost class by measuring.

1

Sum 1000 in a loop.

a = list(range(1000)) s = 0 for x in a: s += x print(s)

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

What it prints

499500

2

Count a nested loop of 20.

n = 20 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

400

3

Sort then search by hand.

a = [5, 2, 9, 1] a.sort() print(a[0], a[-1])

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

What it prints

1 9

4

Sorted versus reversed compare.

best = sum(1 for i in range(4) if i < 4) worst = sum(1 for i in range(4) for j in range(4)) print(best <= worst)

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

What it prints

True

5

Memory of a list of 1000.

a = [0] * 1000 print(len(a))

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

What it prints

1000

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 class predicts the shape; measurement confirms the constant. Time and memory both set real limits.

1 predict the class

↓

2 time two sizes

↓

3 compare the growth

↓

4 check memory too

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 = list(range(1000)) sets nothing on screen

s = 0 sets nothing on screen

for x in a: sets nothing on screen

s += x sets nothing on screen

print(s) 499500

Why this works

Model first, measure second

The class predicts the shape. Measurement confirms the constant and finds the surprises the model missed.

Real limits include memory

A cost class counts steps. Real runs also hit a memory limit, which the step count does not see.

Examples

Time a loop

import timeit
n = 1000
t = timeit.timeit(lambda: sum(range(n)), number = 1)
print(int(t * 1000000))

Microseconds for a thousand adds. The number is small but the shape is what you compare.

Compare two shapes

import timeit
n = 200
a = timeit.timeit(lambda: sum(range(n)), number = 100)
b = timeit.timeit(lambda: sum(1 for i in range(n) for j in range(n)), number = 1)
print(a < b)

The quadratic one is far slower. The gap widens as n grows.

Constant hides work

import timeit
n = 1000
a = timeit.timeit(lambda: sorted(range(n, 0, -1)), number = 10)
b = timeit.timeit(lambda: list(range(n)), number = 10)
print(a > b)

Sorting reversed data costs more than building a list. The library call is not free.

Input order matters

import timeit
best = timeit.timeit(lambda: sorted([1, 2, 3, 4]), number = 1000)
worst = timeit.timeit(lambda: sorted([4, 3, 2, 1]), number = 1000)
print(best <= worst)

Already sorted data is faster to sort than reversed data. The best case is real.

Cache misses cost

a = list(range(1000))
s = 0
for x in a:
    s += x
print(s)

Walking a list in order is fast. Jumping around the same data is slower for the same step count.

Memory is a limit

n = 1000000
a = [0] * n
print(len(a))

A million slots is real memory. A linear algorithm can still fail because of space, not time.

Measure the shape

import timeit
for n in (100, 200):
    t = timeit.timeit(lambda: sum(range(n)), number = 100)
    print(n, round(t, 4))

Double n and a linear cost roughly doubles. That confirms the class.

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.

← Amortized cost

Previous Lesson

Amortized cost

Next Lesson

Space complexity

Space complexity →