Python 7.1The video for this lesson is on its way.
Everything else is ready: study the parts, the key terms and the quiz below.
Python 7.1Code walkthrough8 parts
Time and Space Complexity
Estimate how running time grows with input size.
Loading your progress…Next: 7.2 Binary Search
In this lesson8 parts
- 01How long does a program take?
- 02Counting operations
- 03Best, worst and average case
- 04Big-O notation
- 05A quadratic function
- 06One line can be a loop
- 07Space complexity
- 08Recap, and your challenge
Key terms
The words this lesson introduces, each in one line. The module’s glossary collects them all.
- average case
- The number of operations for a typical input. For a linear search of a value that is present, about half the list.
- best case
- The fewest operations any input of size n needs: a linear search that finds its value first time makes one comparison.
- Big-O notation
- How the number of operations grows, with constants and smaller terms dropped:
4n + 4is O(n). - constant time
- O(1): the same number of operations however large the input, such as
values[0]orlen(values). - linear search
- Checking the values one at a time from the start: O(n).
- linear time
- O(n): ten times the input, ten times the operations.
- operation
- One step we count, here a comparison.
- quadratic time
- O(n²): doubling the input quadruples the operations, as comparing every pair does.
- space complexity
- How the extra memory a function uses grows with the size of its input.
- time complexity
- How the number of operations grows with the size of the input.
- 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).
- 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.
Quiz 5 questions
Your first pick on each question is the one that counts, and a right one earns a coin. Getting one wrong here is how the lesson sticks.
Practice
Problems to solve in your own notebook. Each states the problem, not the steps: working out the steps is the exercise. Level A applies the lesson, B combines it with earlier ones, C stretches it.
The self-checking notebook for this lesson is Notebook 1 · Time and Space Complexity.
Common mistakes
What you will see when it goes wrong, why it happens, and the fix.
Where it’s used
Where this lesson’s ideas turn up in real work.