Time and Space Complexity3 lessons and their Study toolkit.
Watch each lesson, answer its quiz, then do its practice. After the last lesson: the module quiz, the project, and the interview questions.
The lessonsin the order to take them.
Glossaryevery term the module introduces.
Each with the lesson that introduces it.
- average case
- The number of operations for a typical input. For a linear search of a value that is present, about half the list. 7.1
- best case
- The fewest operations any input of size n needs: a linear search that finds its value first time makes one comparison. 7.1
- Big-O notation
- How the number of operations grows, with constants and smaller terms dropped:
4n + 4is O(n). 7.1 - constant time
- O(1): the same number of operations however large the input, such as
values[0]orlen(values). 7.1 - linear search
- Checking the values one at a time from the start: O(n). 7.1
- linear time
- O(n): ten times the input, ten times the operations. 7.1
- operation
- One step we count, here a comparison. 7.1
- quadratic time
- O(n²): doubling the input quadruples the operations, as comparing every pair does. 7.1
- space complexity
- How the extra memory a function uses grows with the size of its input. 7.1
- time complexity
- How the number of operations grows with the size of the input. 7.1
- trade-off
- Using more of one resource, memory or time, to use less of the other: a set spends O(m) memory to make each check O(1). 7.1
- worst case
- The most operations any input of size n needs: a linear search for an absent value compares with all n. Complexity is quoted for the worst case unless it says otherwise. 7.1
- binary search
- Finding a value in a sorted list by comparing it with the middle of the range, and keeping the half that can still hold it. 7.2
- logarithmic time
- O(log n): the operations grow by one each time n doubles. Binary search on 1,000,000 values makes at most 20 comparisons. 7.2
- bucket
- One slot in a hash table. A key's hash, modulo the number of buckets, chooses its bucket. 7.3
- collision
- Two keys in the same bucket, such as
46and22in a table of eight buckets. 7.3 - hash function
- A function that turns a value into an int, the same int every time for the same value. Python's is
hash(). 7.3 - hash table
- A list of buckets, where a value's hash decides its bucket, so a lookup compares only with the keys in one bucket. Every Python
setanddictis one. 7.3 - load factor
- The number of keys divided by the number of buckets. A lookup's work grows with it. 7.3
Module quiz15 questions across it all.
Take it after the last lesson. Your first pick on each question is the one that counts.
Project: log-toolsbuild it without a template.
Stated as a problem, with no step-by-step instructions. Working out the steps is the point.
The task
Create a project log-tools with uv init. In src/log_tools/, write three
functions, each with its time and space complexity in its docstring:
unique_in_order(names), which removes duplicates and keeps the first of each, in O(n);first_at_or_after(timestamps, t), which finds the first entry at or aftertin a sorted list, withbisect, in O(log n);common(a, b), which returns the values in both lists, in the order ofa, in O(n + m).
Write pytest tests for each, including an empty list and a value that is
absent. Write a script that times each against its slow version (a list for
seen, a scan, a nested loop) at 1,000 and 10,000 items. Make Ruff and mypy
report nothing.
Notebooksthat check your answers.
Open them in Google Colab. Each answer is checked as you go: correct, wrong with the expected value, or not answered yet.
- Notebook 1 · Time and Space ComplexityLessons 7.1 Courses plan
- Notebook 2 · Binary SearchLessons 7.2 Courses plan
- Notebook 3 · Hash TablesLessons 7.3 Courses plan
Referencefor revising and for interviews.
The cheat sheet is one page of the module’s terms, rules and gotchas. The interview questions come with model answers.