Big O and basic structures

Learning outcome

By the end of this lesson, you will be able to explain Big O notation, compare common data structures by their performance, and choose the right one for a simple problem.

Why performance matters

A program that takes one second with 10 items might take 10 seconds with 100 items or 10,000 seconds with 10,000 items — depending on how it is written. Understanding how fast your code runs lets you design programs that stay fast as they grow.

Big O notation

Big O describes how the runtime of an algorithm grows as the input size grows. It ignores constant factors and focuses on the trend:

• O(1) — Constant time. Takes the same time regardless of input size. Looking up an item in a dictionary by key.
• O(n) — Linear time. Time grows proportionally with input size. Scanning a list for a value.
• O(n²) — Quadratic time. Time grows with the square of input size. Comparing every item against every other item.

flowchart LR
  A[Input size n] --> B[O(1): flat line]
  A --> C[O(n): straight diagonal]
  A --> D[O(n²): steep curve]
  B --> E[Fast]
  C --> E
  D --> F[Slow for large n]

Lists vs dictionaries

Python gives you two fundamental data structures:

List

A list is an ordered sequence. You access items by their position (index):

fruits = ["apple", "banana", "cherry"]
print(fruits[0])  # "apple"
fruits.append("date")  # O(1) at the end
fruits.insert(0, "apricot")  # O(n) — shifts everything

Looking up an item by value requires scanning the whole list: O(n).

Dictionary

A dictionary (or dict) stores key-value pairs. You access items by key:

prices = {"apple": 0.5, "banana": 0.3}
print(prices["apple"])  # 0.5, O(1)
prices["cherry"] = 0.4  # O(1)

Looking up a key is O(1) — much faster than a list. Use dictionaries when you need to look things up by name.

When to use each

| Use case | Structure | Why | |----------|-----------|-----| | Ordered sequence of items | List | Preserves order, simple iteration | | Look up by key | Dictionary | Fast O(1) lookup | | Unique items, no order needed | Set | Membership test is O(1) | | First-in-first-out queue | List (with collections.deque) | Efficient appends and pops from both ends |

Common beginner mistakes

• Using a list when you need dictionary-style lookups. Scanning a list of 10,000 users by name every time is slow. Use a dict keyed by name.
• Forgetting that in on a list is O(n). if x in my_list scans the entire list. On a set or dict, it is O(1).
• Ignoring performance until it is too late. Design with the right data structure from the start. Optimising later is harder.

Practice task

Write a small program that creates a list of 10,000 numbers, then measures how long it takes to find a specific number using in. Do the same with a set. Compare the times.

Recap

• Big O describes how runtime grows with input size.
• O(1) is constant, O(n) is linear, O(n²) is quadratic.
• Lists are ordered but slow for lookups (O(n)).
• Dictionaries are fast for key lookups (O(1)) but unordered.
• Choose the right structure based on how you access the data.

Next step

Now that you understand algorithms and data structures, the next lesson traces how source code becomes a running API — connecting interpreters, compilers, databases, and HTTP.