Python · Module 7
Time and Space Complexity
Take each lesson, answer its quiz, then do its practice. After the last lesson come the module quiz, the project and the interview questions.
Lessons
Module material
Take these after the last lesson, in this order. Next on each page leads through them.
- Module quiz15 questions across the whole module. Take it after the last lesson; your first pick on each question is the one that counts.
- Project: log-toolsStated as a problem, with no template and no step-by-step instructions. Working out the steps is the point.
- NotebooksOpen them in Google Colab. Each answer is checked as you go: correct, wrong with the expected value, or not answered yet.
- Cheat sheetOne page of the module’s terms, rules and gotchas, with the output each rule produces.
- Interview questions25 questions interviewers ask on time and space complexity, from first principles to the follow-ups. The first 3 model answers are free to read; Pro opens the rest.
Glossary
Every term the module introduces, with the lesson that introduces it.
- average case
- The expected operation count under a stated distribution of inputs. For n distinct values with equally likely successful targets, linear search averages (n + 1) / 2 comparisons. Duplicates or unequal target probabilities change this mean. 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
- An asymptotic upper bound on growth. These lessons use the tightest usual bound, dropping constants and smaller terms:
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 memory use grows with input size. Extra storage excludes the input; auxiliary space also excludes the returned output. State which is being counted. 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