Python for a Coding Assessment
A refresher path through the Python graph for someone who has written Python before and has an assessment coming: run and read, rebuild the core, then work the way an assessment expects.
Analyse what Python code costs
I can say how the running time and memory of a piece of Python grow with its input, name the operation responsible, and measure to check that I am right.
- Domain
- Python Programming
- Level
- advanced
- Status
- draft · v0.1.0
- Also called
- Big-O, Time complexity, Performance, Algorithmic complexity
- License
- CC BY-SA 4.0
Learn first
- Choose the right built-in data structure foundation
- Iterate and transform data in Python foundation
Learn it
Scope
Reasoning about how code behaves as the input grows, in Python’s terms: the costs its own data structures have, and what the interpreter does that a language with manual memory does not.
In scope: reading growth off a function, the common quadratic mistakes, the difference between a constant factor and a growth rate, and measuring. Out of scope: proving bounds formally, amortised analysis, and profiling a large system.
Reading growth off a loop
Count how many times the innermost work happens as a function of input size n.
- One pass over
nitems is linear, O(n). - A loop inside a loop, both over
n, is O(n²) — a thousand items becomes a million operations. - Halving the problem each step, as binary search does on sorted data, is O(log n).
- Sorting is O(n log n), which is close enough to linear to be affordable and is usually the right trade when it unlocks a cheaper algorithm.
The line to find is the one executed most, not the one that looks complicated.
The quadratic mistake, which is nearly always the same one
for item in items: if item in seen_list: # walks seen_list every time ...Membership in a list is O(n), so this is O(n²) and it looks like two innocent lines. A set or a dict
makes the test O(1) and the whole loop linear. This is the single highest-value thing in the node,
and the reason choose-a-python-data-structure comes first.
Its cousins: building a string with += in a loop (each addition copies the whole string; use
join), and calling list.insert(0, x) repeatedly (each shifts everything; use a deque).
Constant factors and when they matter
A change that makes code twice as fast has not changed how it grows. At a thousand items nobody notices; at ten million, the growth rate decides whether the program finishes. Fix the growth first, then, if it still matters, the constant.
Python’s constants are large — an interpreted loop is far slower than a C loop — which is why pushing work into built-ins, comprehensions and library functions written in C often beats micro-optimising Python statements.
Measure, because you will be wrong
timeit runs a snippet many times and reports the best result, avoiding the noise of a single run.
Measure the real input size, not a toy one: the whole point of growth is that behaviour at ten items
tells you nothing about ten million.
Common misconceptions
- “O(n²) is fine, the data is small.” Until someone runs it on the real file. State the assumption in a comment if you rely on it.
- “Big-O tells you which is faster.” It tells you how each grows. For small inputs the “worse” algorithm frequently wins.
- “Comprehensions are an optimisation.” They are a readability choice with a small constant-factor win. Data structure choice is the optimisation.
- “Python is slow, so this does not matter.” Growth rate is language-independent. A quadratic algorithm in C is still quadratic.
Notes for teachers
Give learners a function that is accidentally quadratic and a file big enough to make it hurt. Ask for the growth rate first, the offending line second, and the fix third — in that order, because guessing at fixes before naming the cause is the habit to break.
Then have them time both versions at two input sizes, so they see the growth rather than a single number.
Resources
| Resource | Kind | Cost | Provider |
|---|---|---|---|
| Python wiki: time complexity of built-in operations | reference | free | Python Software Foundation |
| timeit: measure execution time of small code snippets | reference | free | Python Software Foundation |
Courses that include it
Prove it
Evidence of mastery
- Given a function, states how its work grows with input size and names the line responsible.
- Identifies a nested loop or a repeated membership test that makes a function quadratic, and fixes it without changing what it returns.
- Distinguishes a change that makes code twice as fast from one that changes how it grows, and says which matters at scale.
- Times two implementations with `timeit` and reports the result honestly, including when the slower-looking one wins.
Assessments that measure it
Python Take-Home Task
A timed take-home in the shape real hiring uses: read messy data, compute a result, test it, and hand over a repository someone else can run.
Credentials that include it
Python Problem Solving
The holder can take an unfamiliar problem, write a tested Python solution someone else can run, and explain what it costs.
What learners show
Nothing to show yet. The publisher last published on 2026-09-20, and no aggregate for this outcome has reached the 50 learners a number needs. Open Degree does not track learners. About learner evidence.