Data structures and the cost of operations

A notebook of customers

Awa runs a shop in Bonamoussadi and writes her customers in a notebook: one name and one phone number per line, in the order they came. To find a number she reads line after line. With 50 customers that is bearable. With 10,000 she will read 5,000 lines on average and, at worst, all 10,000. Had she kept the notebook in alphabetical order, she would open it in the middle, see whether the name sought comes before or after, and keep only the right half — the way you look up a word in a dictionary. Same notebook, same content: how it is laid out changes everything.

The vocabulary of cost

We measure an operation's cost in elementary steps (a comparison, a read) as a function of the number n of elements. Three operations come up everywhere:

• lookup: finding a given element;
• insertion: adding an element;
• traversal: visiting every element, for instance to display them all. It costs at least n steps whatever the structure: you cannot visit n elements in fewer than n visits.

We write the order of growth with "big O" notation: O(n) means "cost grows in proportion to n", O(log n) "cost grows like the number of times you can halve n", O(1) "cost does not depend on n". The notation deliberately ignores constants ("3n" and "n" are both O(n)); we come back to this in the last lesson.

The linear scan

Go through in order, until you find it or run out of list. At worst (the element is absent or last) it takes n comparisons.

Binary search

It requires a sorted array. Compare the target with the middle element; depending on the result keep the left or right half, and repeat.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return None

Note: Python has no three-way comparison, and this code makes up to two per step (== then <). In this course we count one three-way comparison per step (like a sorting comparator in C, which returns a negative, zero or positive number): that is the convention of the table below.

Worked example. Sorted array [3, 8, 14, 21, 29, 35, 42], target 35. First middle: index 3, value 21; 21 < 35, keep the right (indices 4 to 6). New middle: index 5, value 35: found in 2 steps, instead of 6 for a scan.

Why so few? At each step at most half of the candidates remain: after k steps, at most n ÷ 2^k. We are done when one is left, hence after about log₂ n steps. In this course's counting convention we count one three-way comparison (equal, smaller, larger) per step, so at worst ⌊log₂ n⌋ + 1 steps:

Multiplying n by 1,000 multiplies the scan by 1,000, but adds only about ten steps to binary search. That is what "scaling" means.

What this does not guarantee

• Binary search only works on sorted data. Sorting itself costs about n × log₂ n comparisons. For a single lookup in 50,000 unsorted items, sorting first costs far more than one scan: it only pays off if you search often.
• Keeping an array sorted has a price at every insertion (lesson 2).
• The "worst case" is not the average case: a scan finds the element around n ÷ 2 on average when it is present. And hidden constants matter for small n: with ten elements the simplest approach is often the fastest.

Recap

Count steps as a function of n: scan = n, binary search ≈ log₂ n (on sorted data). A full traversal always costs at least n. The "worst case" gives a guarantee, not a prediction.

Finding a customer without reading the notebook

In the previous lesson, even with binary search, Awa still has to sort her notebook and keep it sorted. What if she could go straight to the right page, like a numbered locker where each customer has a drawer? That is the idea of the hash table. To understand it, start from the simpler structure it derives from: the array.

The array (Python list)

An array stores its elements side by side in memory. Element number i is found by a simple address calculation: access by index in O(1). On the other hand:

In Python, x in my_list is a scan. my_list.insert(0, x) shifts everything. For a queue where you remove on the left, the collections.deque structure is made for it.

The hash table (dict, set)

A hash table has a number of buckets. A hash function turns a key (a name, a number) into a number; take that number modulo the number of buckets to get the bucket where the key is stored. Finding the key means redoing the same calculation and going straight to the bucket — without walking through the others.

Example with a TOY function. A table of 8 buckets; the "function" adds up the letters' codes, then takes the remainder of division by 8. (Real functions are much better; this one is to see the mechanics.)

"Aaw" lands in the same bucket as "Awa": a collision. Two different keys, one bucket. The classic fix, chaining, keeps a small list in each bucket: new keys are added at the end, and to search you compare, in order, the keys of the bucket. Searching "Aaw": compute bucket 1, compare with "Awa" (no), then "Aaw" (yes): 2 comparisons, instead of reading the whole notebook.

As long as the function spreads the keys well and the table is not too full, each bucket holds very few keys: lookup, insertion and deletion cost O(1) on average. When the table gets too full it is enlarged and all keys are placed again: one exceptional insertion costs O(n), but spread over all insertions it stays O(1) "amortised".

In Python: set(my_list) builds a table; "Mba" in my_set hashes "Mba" and looks at one bucket. On a million elements, the difference with in on a list is a million comparisons against a handful.

What this does not guarantee

• The worst case is O(n). If all keys land in the same bucket, the table becomes a plain list. That is rare with a good hash function… unless someone causes it on purpose: see the security exercise.
• No sorted order. A hash table cannot answer quickly "the customers between D and K" or "the smallest". (A Python dict remembers insertion order since Python 3.7, but that is not key order.)
• It costs memory: empty buckets are kept in reserve.
• Chaining is our teaching model, not Python's internal detail. CPython's dict and set use open addressing (on a collision they look for another free slot) rather than a list per bucket; the cost story (O(1) on average, O(n) worst case) is the same, but the picture of "a small list in each bucket" is not what Python does inside.
• Keys must be immutable: if a key changes afterwards, its bucket is no longer the right one.
• This hash function has nothing cryptographic about it: it only tries to spread. The functions that protect data are the subject of workshop 104.

Recap

Array: access by index in O(1), search in O(n) (or O(log n) if sorted, but insertion in O(n)). Hash table: lookup and insertion in O(1) on average, but no order, with an O(n) worst case when keys pile up.

A directory that accepts new customers

The sorted array searches fast but inserts badly; the hash table searches and inserts fast but ignores order. Is there a structure that does both — search in O(log n), insert in O(log n), and stay sorted? Yes: the binary search tree (BST).

The principle

Each node holds a key and up to two children: smaller keys to the left, larger keys to the right. To search, start at the root and, at each node, compare: go left or right, never both.

Insert 50, 30, 70, 20, 40, 60, 80 in that order into an empty tree:

50
  left : 30
    left : 20
    right: 40
  right: 70
    left : 60
    right: 80

Search for 60: compare with 50 (60 is larger, go right), with 70 (smaller, go left), with 60 (found): 3 comparisons, for 7 keys. A tree of height h (number of levels) is walked from the root to a leaf in at most h comparisons. If the tree is well balanced, h ≈ log₂ n: for a million keys, about 20 levels.

In-order traversal

The big advantage over the hash table: visiting the tree "left, node, right" (an in-order traversal) yields the keys sorted: 20, 30, 40, 50, 60, 70, 80. The cost is O(n), the minimum possible. And a range query ("all keys between 35 and 65") first descends towards 35 in O(log n), then walks in order up to 65: it visits only what is needed. A hash table would have to examine all n keys.

The trap: the unbalanced tree

Now insert 10, 20, 30, 40, 50 — keys already sorted — into an empty tree. Each new key is larger than all the previous ones, so it always goes right:

10
  right: 20
    right: 30
      right: 40
        right: 50

The tree has become a linked list: finding 50 takes 5 comparisons, and with n sorted keys, n comparisons. The O(log n) guarantee depends on balance. Self-balancing trees (red-black trees, AVL trees…) reorganise on insertion to keep the height close to log₂ n. Databases use variants with many children per node, B-trees: SQLite stores its tables and indexes in B-trees. You will meet them again in workshop 103.

Comparing the four structures

(k = number of results returned.)

What this does not guarantee

• A plain BST does not balance itself: everything depends on the order in which keys arrive.
• The tree is slower than the hash table for a pure exact lookup (log n against ≈ 1), more work to write, and its nodes scattered in memory suit the processor less well than a contiguous array.
• The "O"s do not predict which will be fastest on 100 elements. Only a measurement says so (lesson 4).

Recap

The balanced tree offers search and insertion in O(log n) and a sorted walk: that is what you buy by giving up the table's O(1). Without balancing, the arrival order can degrade it into a list.

Which structure for which job?

There is no "best" structure, only trade-offs. To choose, start by describing the access profile: what the program really does, and in what proportions.

1. How big? How many elements today, and in a year?
2. Which operations dominate? Exact lookup, insertion, deletion, full traversal, range query, "the smallest"?
3. Does order matter? Do we need the data sorted?
4. How often? Once a day or a thousand times a second?

A few cases:

In a blockchain you will meet these profiles again: finding a balance by address (exact lookup, hash table), walking the blocks in order (ordered list), checking that a piece of data belongs to a set (later workshops).

Measure instead of estimating

O notation says how the cost grows, not how many milliseconds it is worth. Two O(n) programs can differ ten-fold. An O(log n) can lose to an O(n) on small arrays. The only way to know is to measure, with method.

import timeit

for n in (1_000, 2_000, 4_000, 8_000):
    items = list(range(n))
    # unfavourable case: the element sought is the last one
    t = min(timeit.repeat(lambda: (n - 1) in items, number=200, repeat=5)) / 200
    print(n, round(t * 1e6, 1), "µs per call")

Good practice for this measurement:

• Time only the operation, not the building of the data.
• Repeat (here 5 series of 200 calls, each series' time being divided by 200 to get the time of one call) and keep the minimum or the median: noise (other programs, caching) can only add time.
• Vary n and watch how the time evolves, rather than trusting one point.
• Do not conclude from very short durations: below a few microseconds you mostly measure the cost of the call.

Reading a doubling

Double n and look at the ratio of the times:

If your prediction ("the hash table should not vary") is not confirmed by the measurement, the measurement is right — then ask why (collisions? resizing? memory exhausted?). If it is confirmed, you have evidence, not an opinion.

What this does not guarantee

A measurement holds for this hardware, this data set and this version of the language. A random data set can hide an unfavourable case (sorted keys in an unbalanced tree); a data set that is too small can hide growth. So say what you measured on, and do not generalise beyond it.

Recap

Describe the access profile before choosing; do not confuse growth (O) with duration; measure by repeating, isolating the operation and varying n; read a doubling to guess the growth; state the limits of your measurement.