You have used lists and dicts for weeks. Now a friend asks a simple question: why is x in my_list slow on a big list, and x in my_set fast? The answer is a way of thinking, not a trick. This lesson gives you the few words and the one habit that the rest of this part uses. Nothing here needs more than the lists and dicts you already know.
Learning Objectives
After this lesson, you will be able to:
Say in one sentence what a data structure is and what an algorithm is, and point to one of each in a short program
Explain what n stands for, and count the steps of a loop as a function of n
Explain log n with the halving game, and say how many guesses a million numbers need
Read O(1), O(log n), O(n), O(n log n) and O(n²) in a piece of code using five short rules
Name the four levels of this part and the lessons in each, and follow the study habit: trace by hand, then code, then five problems
Look up the cost of an operation on a list, dict, set, deque, heap or sorted list on the cheat sheet
This part of the track is optional. You do not need it to finish the core path. It is the classic computer science depth, and this lesson is its front door.
A data structure is a way of keeping many values together so that some jobs are easy. A list keeps values in order, so "give me the third one" is easy. A dict keeps pairs, so "what is Asha's score?" is easy. Every structure makes some jobs fast and others slow, so choosing one means choosing which jobs you want to be fast.
An algorithm is a list of steps that solves a problem and finishes. A recipe is one. So is finding the biggest number in a list: look at each number, remember the largest so far, and stop at the end.
pythonrunnable cell
1
2
3
4
5
6
7
8
9
scores = [72, 91, 65, 88] # the data structure: a list
best = scores[0]
for s in scores: # the algorithm: look at each value, keep the largest
if s > best:
best = s
print(best)
# Output:
# 91
The two go together. The structure holds the values, and the algorithm works on them. The same job can be done in different ways, and the ways can differ a lot in cost. Cost here means the number of steps the computer takes. Most of this part is about spotting that cost before you run anything.
The letter n is the size of the input: how many values your program has to handle. If your list has 1,000 scores, n is 1,000. If a file has a million rows, n is a million.
Why use n? Because we want to say how the work grows when the data grows. We count steps and not seconds. A step is one small action: compare two values, read one cell, add two numbers. Seconds depend on your laptop and on what else it is doing. Steps depend only on the algorithm and on n.
This function does a linear search. It looks at the values one by one until it finds the target. The cell counts the steps it takes when the target is the last value.
pythonrunnable cell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def count_steps(items, target):
steps = 0
for x in items:
steps += 1 # one step: look at one value
if x == target:
break
return steps
for n in (10, 100, 1_000):
items = list(range(n))
print(n, count_steps(items, n - 1))
# Output:
# 10 10
# 100 100
# 1000 1000
Ten times more values means ten times more steps. We say the cost grows in line with n. Hold on to that picture, because the next idea is the one where the cost hardly grows at all.
Think of a guessing game. A friend picks a whole number from 1 to 8. After each guess they say "higher" or "lower". You always guess the middle of what is left.
With 8 possible numbers you guess 4. Whatever the answer, at most 4 numbers are left. Guess the middle of those, and at most 2 are left. Guess again, and 1 is left. The numbers that could still be right go 8, 4, 2, 1. That is at most 4 guesses, even though there were 8 numbers.
Each guess throws away half of the choices. That is the whole idea behind log n. It means: how many times can you cut n in half before nothing is left? When n doubles, you need just one more cut. That is why log n grows so slowly.
What Do You Think?
A friend thinks of a whole number from 1 to 1,000,000. You always guess the middle of what is left, and they say higher or lower. At most how many guesses do you need?
The cell below plays the game for every possible secret number and keeps the worst result. Next to it, a counter does nothing but cut n in half. The two columns match.
pythonrunnable cell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def worst_guesses(n):
"""Play the halving game once for every secret number from 1 to n; keep the worst."""
worst = 0
for secret in range(1, n + 1):
low, high, count = 1, n, 0
while low <= high:
count += 1
mid = (low + high) // 2
if mid == secret:
break
if mid < secret:
low = mid + 1
else:
high = mid - 1
worst = max(worst, count)
return worst
def halvings(n):
"""How many times can n be cut in half (rounding down) before nothing is left?"""
cuts = 0
while n > 0:
n //= 2
cuts += 1
return cuts
for n in (10, 100, 1_000, 10_000):
print(n, worst_guesses(n), halvings(n))
print(1_000_000, halvings(1_000_000))
print(1_000_000_000, halvings(1_000_000_000))
# Output:
# 10 4 4
# 100 7 7
# 1000 10 10
# 10000 14 14
# 1000000 20
# 1000000000 30
A thousand times more numbers (a million instead of a thousand) cost only 10 more guesses. This is exactly what binary search does on a sorted list, and the Big-O and searching lesson builds it. The same halving shows up in sorted trees and in heaps, where a structure is a few levels tall and each step moves down one level. In Big-O we write log n and ignore the small extra step.
Big-O describes how the number of steps grows as n grows. You read O(n) as "order n". Before the rules, try one loop.
What Do You Think?
The list items holds 1,000 values. What does count hold at the end?
count = 0
for a in items:
for b in items:
count += 1
Here are the five rules. They are enough to read most code in this part.
Count steps as a function of n, and ignore the seconds.
Loops one after another add their steps. A loop inside a loop multiplies them.
Keep only the part that grows fastest and drop the constants. So 3n + 50 steps is O(n), and n times n over 2 steps is O(n²).
If each pass cuts the work in half, the cost is log n.
Big-O is about large n. It tells you how the cost grows, and not how long one run takes.
Here is what each class means for 1,000 values and for a million. The numbers are rounded.
Class
Plain meaning
n = 1,000
n = 1,000,000
O(1)
the same steps whatever n is
1
1
O(log n)
the work halves at every step
10
20
O(n)
touch each value once
1,000
1,000,000
O(n log n)
halve repeatedly, touching everything at each level
10,000
20,000,000
O(n²)
every value against every value
1,000,000
1,000,000,000,000
One more piece of language, because the cheat sheet uses it. The worst case is the input that makes the algorithm work hardest. The average case is a typical input. Amortized means averaged over a long run of operations: a list.append is usually one step, and now and then it must make room and copy the list, but over many appends the average is one step. When a cost below says "average" or "amortized", this is what it means. A plain O(...) with no label is true for every input.
The lessons in this part form a path with four levels. You read them in the order listed. Level 0 is in the core path already, so it is a warm-up. The other levels are the optional part.
Level 0, the warm-up. These give you the tools Python already has.
Data Structures: lists, tuples, dicts and sets, and the cost of their everyday operations.
Algorithms are learned by doing, not by reading. Use the same three steps for every lesson.
Trace by hand first. Before you type a line, take a tiny input and run the algorithm on paper. Write the variables in a table and update one row per step. Here is the "biggest value" loop on [4, 9, 2].
Step
x
best after this step
start
4
1
4
4
2
9
9
3
2
9
Then write the code. Now the code is only a translation of a table you already understand. When the output is wrong, compare it with your table, row by row, and the first row that differs is the bug.
Then climb the five-problem ladder. After a lesson, solve five problems in this order, and do not skip a rung. First, the lesson's example with one thing changed. Second, a small variation. Third, the idea combined with something you learned earlier. Fourth, a program with a bug that you must find. Fifth, make it faster and say its Big-O. If you are stuck for fifteen minutes, read a hint, close it, and try again.
Keep a notebook with two columns: the problem, and the one idea that solved it. After a month, the right column is your own cheat sheet.
This is the page to bookmark. Every cost below is documented CPython behaviour, and the Try It section lets you check the big ones by counting. "avg" means average case, and "amort." means amortized, as explained above.
Operation
list
dict
set
deque
heap (heapq)
Add one value
append: O(1) amort.
d[k] = v: O(1) avg
add: O(1) avg
append, appendleft: O(1)
heappush: O(log n)
Remove one value
pop() from the end: O(1)
del d[k]: O(1) avg
The same table for sorting and searching.
Job
Cost
What to remember
sorted(a)
O(n log n) time, O(n) extra space
returns a new list and leaves a alone
a.sort()
O(n log n) time, in place
returns None. On a list that is already sorted, it takes about n steps
bisect.bisect_left(a, x)
O(log n)
needs a sorted list
bisect.insort(a, x)
O(n)
the search is O(log n), but shifting values over to make room is O(n)
min(a), max(a)
Three lines to remember from the tables:
x in a_list looks at up to every value, while x in a_set or k in a_dict goes straight to the place where it would be.
list.pop(0) shifts every other value over by one, so it is O(n). deque.popleft() is O(1), which is why a queue should be a deque.
heap[0] is the smallest value and costs nothing. Taking it out with heappop costs O(log n), because the heap must fix itself.
A note on the word "average" for dict and set. They are O(1) on average. In a very unlucky case, when many keys land in the same place, a lookup can take O(n). Python's hashing makes that rare enough that the average is the number to plan with.
Check two rows of the cheat sheet yourself. A value class below counts every == and every < it takes part in. We count comparisons and not seconds, so the numbers are the same on every machine. Run it, then change the sizes and predict what will happen before you press run.
pythonplayground.py · Pyodide
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Tests · list= prints n (1000, 2000, 4000), set= and dict= print 1, and sorted(already sorted) prints n - 1.
A data structure keeps values together so some jobs are easy, and an algorithm is the list of steps that does a job. The letter n is the input size, and we count steps as a function of n and not seconds. The halving game explains log n: each guess cuts the choices in half, so a million numbers need about 20 guesses and doubling n adds one.
Read Big-O with five rules: count steps, add loops side by side and multiply nested ones, keep the fastest-growing part, halving means log n, and Big-O is about large n. The lessons ahead run in four levels, from the warm-up tools, through Foundations and Core and Advanced, to Expert. Study each by tracing on paper, then coding, then solving five problems in order. The cheat sheet gives the cost of the everyday operations on a list, dict, set, deque, heap and sorted list.
Quick Check1 / 6
A function runs 4,000 steps on 1,000 values and 8,000 steps on 2,000 values. Which growth does that suggest?
Recap
Key Takeaways
1A data structure keeps values together so some jobs are easy, and an algorithm is the list of steps that does a job
2n is the input size, and we count steps as a function of n, not seconds
3log n means how many times you can cut n in half, so a million needs about 20 and doubling n adds one
4Loops side by side add, a loop inside a loop multiplies, and you keep only the fastest-growing part
5Study by tracing on paper, then coding, then solving five problems in order
6Check the cheat sheet before you pick a structure: list membership is O(n), set and dict are O(1) on average, and a queue should be a deque
How CPython Works: not about algorithms; it looks inside Python itself.