Two functions can return the right answer and still be wildly different in practice. Sum a list of a thousand numbers and your program finishes before you blink; compare every possible pair in a list of a thousand numbers and it performs half a million operations. The answers may be identical; the cost is not.
Time complexity is how we talk about that cost as the input grows. It does not measure seconds — those depend on your hardware and your data — it measures how the number of steps scales when you hand the function ten items instead of ten thousand. That scaling, written in Big O notation, is the difference between code that holds up under real load and code that collapses the first time a user gives it a big file.
This lesson introduces the growth rates you will meet in everyday Python and the single decision — list versus set — that turns a slow program into a fast one.
flowchart LR N["input size n"] --> O1["O(1): stays flat"] N --> On["O(n): climbs steadily"] N --> On2["O(n^2): explodes"] style O1 fill:#1e293b,color:#fff style On fill:#3776ab,color:#fff style On2 fill:#b45309,color:#fff
Big O in one idea
Big O describes the upper bound on how work grows with input size, written as a function of n. O(1) means the work is constant — it does not grow at all, no matter how large the input. O(n) means the work grows in step with the input: twice the data, roughly twice the work. O(n²) means it grows with the square of the input: twice the data, four times the work.
Notice what Big O ignores. It ignores constant factors and it ignores small inputs. Doubling ten items matters little; what matters is the shape of the curve as n climbs. That shape is what you choose when you pick an algorithm or a data structure.
def total(numbers):
result = 0
for n in numbers:
result += n
return result
print(total([1, 2, 3, 4, 5]))
When loops nest, costs multiply
A single loop over n items is O(n) — it touches each item once. When you place one loop inside another over the same data, the inner loop runs n times for every one of the n outer steps, giving n × n = n² work. That is O(n²), and it is the most common way beginners write accidentally slow code.
For ten items the difference is invisible: one hundred steps instead of ten, both instant. For ten thousand items it is the difference between ten thousand steps and one hundred million — the difference between instant and frozen. Nested loops are not wrong, but each one you add multiplies the cost, so they deserve a second look whenever the input might grow.
flowchart TD Q["is 'pear' in items?"] --> L["list: scan each item<br/>until found — O(n)"] Q --> S["set: hash jump<br/>straight to the answer — O(1)"] style L fill:#b45309,color:#fff style S fill:#3776ab,color:#fff
The one decision that matters most: list or set
Here is the trap that catches almost everyone. Checking "pear" in fruits reads the same whether fruits is a list or a set, but the cost is not the same at all. A list checks membership by scanning every element until it finds a match — O(n). A set uses a hash table to jump straight to the answer — O(1).
For a handful of items you will never notice. For a program that checks membership against ten thousand items, inside a loop that runs ten thousand times, the list version does up to a hundred million comparisons while the set version does ten thousand. Same code shape, same correct answer, a million-fold difference in work.
The rule that falls out of this is simple and powerful: if you check membership more than once, store the items in a set. Build the set once — an O(n) step — and every lookup after that is effectively free.
fruits = {"apple", "banana", "cherry"}
print("banana" in fruits)
print("grape" in fruits)
Dictionaries get the same speed
A dictionary is a hash table for its keys, so looking up prices["apple"] is O(1) — constant time, just like a set. That is why counting or grouping with a dictionary scales well: you can update a count for each of a million words, and each update is a single hash lookup rather than a scan.
When you need to look something up by a key — a name, an id, a code — reach for a dict. When you only need to know whether something belongs to a collection, reach for a set. Both give you the constant-time lookups that keep a program fast as the data grows.
words = ["apple", "banana", "apple", "cherry", "banana"]
counts = {}
for w in words:
counts[w] = counts.get(w, 0) + 1
print(counts)
flowchart TD A["check membership<br/>more than once?"] -->|"yes"| B["use a set<br/>O(1) lookups"] A -->|"no"| C["a list is fine<br/>O(n) once"] style B fill:#3776ab,color:#fff style C fill:#1e293b,color:#fff
Write count_vowels(text) that returns the number of vowel letters (a, e, i, o, u) in text, case-insensitively. A single pass over the string is O(n).
def count_vowels(text):
# loop once, count a/e/i/o/u
pass
Lowercase the text first with text.lower().
Count characters that are in the set 'aeiou'.
def count_vowels(text):
vowels = set("aeiou")
return sum(1 for ch in text.lower() if ch in vowels)
A function loops over a list of n items, and inside that loop it loops over the same n items again. What is its time complexity?
One loop over n is O(n); nesting a second loop over n makes the inner run n times for each outer step, so the work is n x n = n^2.
This is meant to return True when a list contains any duplicate value, but it always returns True — the inner loop compares each element to itself. Rewrite it so a set makes the check both correct and O(n).
def has_duplicate(nums):
for i in range(len(nums)):
for j in range(len(nums)):
if nums[i] == nums[j]:
return True
return False
A set drops duplicates, so set([1, 2, 2]) is {1, 2}.
If the set is shorter than the list, a duplicate existed.
def has_duplicate(nums):
return len(nums) != len(set(nums))
You must check whether a value appears in a collection of 10,000 items, and you will do this thousands of times. Which structure makes each check fastest?
A set uses a hash table, so membership tests are O(1) — constant time regardless of size. A list scans element by element (O(n)), so thousands of checks against 10,000 items become millions of comparisons.
Write count_common(a, b) that returns how many values of list a also appear somewhere in list b. Convert b to a set first so each lookup is O(1) rather than scanning b every time.
def count_common(a, b):
# convert b to a set, then count a's items that are in it
pass
Build b_set = set(b) once, before the count.
Count each item of a that is in b_set.
def count_common(a, b):
b_set = set(b)
return sum(1 for item in a if item in b_set)
Recap
- Big O describes how work scales with input size, not how many seconds it takes.
- A single loop is
O(n); a loop nested inside another over the same data isO(n²). - Membership tests on a list are
O(n)(a scan); on a set or dict they areO(1)(a hash jump). - If you check membership more than once, store the items in a set — build it once, then look up for free.
Next you will measure real code to find its bottlenecks, instead of guessing where the time goes.