PHASE 4Beginner ~28 min· topic 11 of 11

Topic 4.11

Choosing the Right Structure and Its Cost

In one line

Every container makes some operations cheap and others expensive. This topic explains Big-O in plain words, compares the cost of the common operations on lists, deques, sets and dictionaries, and gives a short guide for choosing on purpose.

Think of it like this

Finding a person in a crowd. If everyone stands in a random line and you check each face, a crowd twice as big takes twice as long. If everyone wears a numbered badge and you have a board that tells you where each number stands, a crowd of any size takes about the same time. Both ways find the person, but they scale differently. How cost grows as data grows is what choosing a structure is about.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Big-O: A way of describing how the work grows as the data grows, ignoring small constants.
O(1): Constant: the work does not grow with the data.
O(n): Linear: the work grows in step with the data.
O(log n): Logarithmic: doubling the data adds one step. Binary search is an example.
O(n²): Quadratic: the work grows with the square of the data, as with a loop inside a loop.
Amortised: Averaged over many operations: an occasional slow one is paid for by many fast ones.
Scale: How well a program copes when the data gets bigger.
Membership test: Asking whether a value is in a collection, using in.

Step by step

01Counting steps instead of seconds

Clocks vary from computer to computer, but the number of steps does not. This program scans a list from the start until it finds the last item and counts the comparisons. 10 items need 10 steps, 1000 need 1000. That is O(n).

main.pywhole filepython

for size in [10, 100, 1000]:
    items = list(range(size))
    steps = 0
    for item in items:
        steps += 1
        if item == size - 1:
            break
    print(size, "items ->", steps, "steps")

02Halving: O(log n)

If the list is sorted, you can look at the middle item, throw away the half that cannot contain the target, and repeat. A million items need only about 20 steps. This is binary search, and bisect does it for you (Topic 4.2).

main.pywhole filepython

items = list(range(0, 2000000, 2))     # a million sorted items
target = 1999998
low, high = 0, len(items) - 1
steps = 0
while low <= high:
    steps += 1
    mid = (low + high) // 2
    if items[mid] == target:
        break
    elif items[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
print(steps, "steps for", len(items), "items")

Halving: O(log n)diagram

Rendering diagram…

03O(1): jump straight to the answer

A dictionary computes where the key is stored and goes there. The number of steps does not depend on the size. Set and dict lookups use the same trick.

main.pywhole filepython

phone_book = {"Asha": "98100", "Ravi": "98200", "Tom": "98300"}
print(phone_book["Tom"])            # one hash, one slot

pairs = [("Asha", "98100"), ("Ravi", "98200"), ("Tom", "98300")]
for name, number in pairs:          # a scan: up to n steps
    if name == "Tom":
        print(number)

04The loop-inside-a-loop trap: O(n²)

if x in big_list inside a loop over another big list is a loop inside a loop. With 10,000 items on each side that is 100 million comparisons. Turning the inner list into a set makes the inner step O(1) and the whole job O(n).

main.pywhole filepython

a = list(range(0, 3000, 3))
b = list(range(0, 3000, 2))

common = [x for x in a if x in b]          # O(len(a) * len(b))

b_set = set(b)
common = [x for x in a if x in b_set]      # O(len(a)) after one O(len(b)) set

05Memory also has a price

A set or dict of 1000 items uses more memory than a list of the same 1000, because the hash table keeps empty slots on purpose. A tuple is a little smaller than the equal list. Exact byte counts differ between computers and Python builds, so compare sizes rather than quoting numbers.

06Measure before you optimise

Real timings depend on your machine, so run the timeit module locally (it is covered in the performance phase). A good habit: write the clear version first; if it is too slow, measure to find where, then change that part.

Try it yourself

1
Change the size
In the first example, change size to 100000 and see how the scan steps change while the binary search steps hardly do. Why does a 10 times bigger list add only 3 or 4 steps to binary search?
2
Spot the O(n²)
In the second example, how many comparisons does the nested loop do? Change 3000 to 6000 for both lists and predict the new count (roughly four times as many).

Code & diagrams

Count the steps: scan, halve, hash New tab

The numbers are steps, not seconds, so they are the same on every computer.

Expected output

list scan: 1000000 steps
binary search: 20 steps
dictionary lookup: 1 hash and 1 slot ( 1000 keys stored )

Same answer, very different work New tab

`sys.getsizeof(x)` tells you how many bytes the object `x` takes in memory. The two `import` lines load ready-made toolboxes (Topic 6.1 teaches import).

Expected output

list in list: 500 common items, 1124750 comparisons
with a set: 500 common items, 1000 lookups
same answer: True
set uses more memory than list: True
tuple not bigger than list: True
popleft: 0 | left: [1, 2, 3, 4]

Which structure? A decision guidediagram

Rendering diagram…

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Use binary search on an unsorted list

Run bisect on a list that is not in order.

main.pywhole filepython

import bisect

items = [5, 1, 4, 2, 3]
position = bisect.bisect_left(items, 2)
print("looking for 2 ->", position, "which holds", items[position])

terminal

$ python main.py

── what you'll see ──

looking for 2 -> 2 which holds 4

Myth vs fact

Myth

O(1) means instant.

Fact

It means the cost does not grow with the data. A single O(1) operation can still be slower than an O(n) one on a tiny list.

Myth

Always use a set or dict because they are fastest.

Fact

They cost memory and need hashable items, and for a small collection a list is just as fast. Choose by the operation you do most.

Myth

Big-O is only for interviews.

Fact

It predicts which program will still work when the data is 100 times bigger, a question every real system faces.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Big-O hides constants and ignores real hardware. A list scan of 100 items can beat a dictionary lookup because of CPU caches and smaller overhead. The point of Big-O is the trend; the timeit module and a profiler give the real numbers (Phase 13).
▸
List append is amortised O(1): the array grows by a proportion each time, so the occasional copy is paid for by many cheap appends. list.insert(0, x) in a loop to build a list is a quiet O(n²); build it with append and reverse once, or use a deque.
▸
x in some_list inside a loop is the most common accidental quadratic in Python. Building a string with += in a loop is the other one in principle: CPython often optimises it when the string has no other references, but that is an implementation detail that other Python implementations lack, so "".join(parts) is the portable habit (Topic 3.5). Spotting both is a core review skill.
▸
Some structures are not in this topic's table because they solve a different problem: heapq keeps the smallest item at the front, so heapq.nlargest(k, items) finds the k biggest in O(n log k) instead of sorting everything in O(n log n); bisect plus a list gives a sorted sequence with O(log n) search but O(n) insertion; and array.array or NumPy store raw numbers instead of pointers. Dictionary and set operations are O(1) on average and O(n) in the worst case (Topic 4.5), so state "average" when you quote them.
▸
In AI work, the data is large enough that it matters: vector search (finding the closest of many lists of numbers, called vectors) over a million embeddings (vectors that stand for the meaning of a text) by scanning is O(n) per query, which is why approximate indexes exist; deduplicating a corpus uses a set of hashes; counting tokens uses a Counter. NumPy (Phase 14) moves the O(n) loops into compiled code, which is a constant-factor win rather than a change of Big-O.

Remember this

1
Big-O is a way of describing how the work grows when the amount of data n (the number of items) grows, ignoring small fixed costs. O(1) (constant): the work stays the same however large n is, like looking up a dictionary key. O(n) (linear): double the data, double the work, like scanning a list. O(log n): doubling the data adds only one extra step, like halving a sorted list again and again (binary search). O(n log n): sorting. O(n²): a loop inside a loop over the same data; double the data, four times the work.
2
For a list: reading or writing items[i] is O(1). append and pop() at the end are O(1) on average. insert(0, x), pop(0) and del items[0] are O(n), because everything shifts. x in items, items.index(x), items.remove(x) and items.count(x) are O(n). Sorting is O(n log n). len(items) is O(1).
3
For a dict and a set: adding, removing and looking up one key or member is O(1) on average (Topic 4.5), and len is O(1). Looping through all of them is O(n). Dictionaries and sets cost more memory per item than a list, because of the hash table's spare room, but they never need a scan to find something.
4
For a deque: append, appendleft, pop and popleft are O(1); indexing in the middle is O(n). For a tuple: like a list for reading, but it can't change. For a sorted list with bisect: finding a position is O(log n), but inserting still has to shift items, which is O(n).
5
A practical guide. Need order and duplicates, index by position? list. Fixed small record, or a key made of several parts? tuple. Look up by a name or id? dict. Unique items, fast "is it in there?", set maths? set. Queue, or fast removal from the front, or a sliding window? deque. Count things? Counter. Group things? defaultdict(list). Need sorted order all the time? keep a sorted list with bisect, or sort when you need it.
6
The most common speed-up in beginner programs is replacing a list with a set or dict for membership and lookup inside a loop. Searching a list of pairs for a name is O(n) per search; turning it into a dictionary makes it O(1). But do not optimise first: for a few hundred items nothing here matters, and clear code wins. Measure before you change (the timeit module, Phase 13) and optimise the part that is actually slow. For a deep treatment of complexity and data structures, see the DSA course (/dsa), which has Python solutions.

Explain it without notes

What does O(1), O(n) and O(n²) mean, with one Python example of each?

Why is x in my_set O(1) but x in my_list O(n)?

When would you use a deque instead of a list?

How would you speed up a loop that checks if name in names against a list of 100,000 names?

How would you find the 3 largest numbers in a list of a million numbers, and what does each approach cost?

Practice

You have emails = [...] with 50,000 items and must test thousands of addresses against it. Show how to set it up for fast tests, using a short example list.

Which container would you use for: (a) the last 5 messages of a chat, (b) the number of times each word appears, (c) unique visitor ids? Print your answers as three lines.

Write a loop that counts how many steps a linear search takes to find 7 in [3, 9, 7, 1] and print the count.

Trade-offs

↔
Time versus memory. Hash-based containers answer lookups in constant time but use more memory than a list. Sorted lists save memory and allow range queries but make insertion slow.
↔
Simple versus fast. The clearest code is usually a list and a loop. Move to a set, dict or deque when the data is big enough that a measured slowdown appears, not before.

Done when you can

Done when you can explain O(1), O(n), O(log n) and O(n²) in plain words with an example each.
Done when you can list the cost of append, insert(0, x), x in, and pop(0) for a list.
Done when you can choose between list, tuple, dict, set and deque for a described task.
Done when you can turn a slow list-membership loop into a fast one with a set.
Done when you can say why sorted input is needed for bisect, and where to learn more (the DSA course).

Command Palette

Words you'll meet

Step by step

01Counting steps instead of seconds

02Halving: O(log n)

03O(1): jump straight to the answer

04The loop-inside-a-loop trap: O(n²)

05Memory also has a price

06Measure before you optimise

Try it yourself

Change the size

Spot the O(n²)

Code & diagrams

Break it on purpose

Use binary search on an unsorted list

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can