Two programs can solve the same problem, but one might take a millisecond and the other a full minute. As the amount of data grows, that gap explodes. Big-O notation is the language we use to describe how an algorithm's work grows as the input gets bigger.
We don't measure in seconds (computers differ!). Instead we count how many steps the algorithm takes relative to the input size, which we call n.
š The common complexities
Big-O
Name
Example
Speed
O(1)
Constant
Get list[0]
š Fastest
O(log n)
Logarithmic
Binary search
ā” Excellent
O(n)
Linear
One loop over a list
š Good
O(n log n)
Linearithmic
Merge sort
š Decent
O(nĀ²)
Quadratic
Nested loops
š¢ Slow
O(2āæ)
Exponential
Naive recursion
š Avoid!
šÆ O(1) ā Constant time
The work is the same no matter how big the data is. Grabbing one item by its index is instant:
def first(items):
return items[0] # one step, always
ā”ļø O(n) ā Linear time
The work grows in direct proportion to the input. One loop = O(n):
def total(items):
s = 0
for x in items: # runs n times
s += x
return s
Double the list, and it takes about double the steps.
š¢ O(nĀ²) ā Quadratic time
A loop inside a loop means n Ć n steps. This gets slow fast ā 100 items = 10,000 steps!
def has_duplicate(items):
for i in items: # n times
for j in items: # n times each
... # n Ć n = nĀ² steps
š The rules of Big-O
Simplify, simplify
Drop constants: O(2n) becomes O(n). We care about growth, not exact counts.
Drop smaller terms: O(nĀ² + n) becomes O(nĀ²). The biggest term dominates.
Worst case: Big-O usually describes the slowest possible run.
ā What you learned
Big-O describes how work grows with input size n.
One loop ā O(n). Nested loops ā O(nĀ²). No loop ā O(1).
Halving the problem each step ā O(log n).
Drop constants and smaller terms when simplifying.
š® Time to Practice!
Reason about speed, then prove it with code. Press ā¶ Run and ā Check.
ā”ļø
Task 1: Write an O(n) Function
Easy
Finish total(items) so it loops once through the list and returns the sum. Calling it on [1,2,3,4,5] should print 15. (This is O(n) ā a single loop.)
def total(items):
s = 0
for x in items:
s += x
return s
print(total([1, 2, 3, 4, 5]))
š¢
Task 2: The O(nĀ²) Duplicate Finder
Medium
Write has_duplicate(items) using nested loops that returns True if any value appears twice. Test on [3, 1, 4, 1] ā should print True. (Compare each pair of different positions.)
def has_duplicate(items):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False
print(has_duplicate([3, 1, 4, 1]))
ā”
Task 3: Make It Fast ā O(n)
Tricky
The same duplicate check can be done in O(n) using a set! Finish has_dup_fast: loop once, remember seen values in a set, return True the moment you see a repeat. Test on [1, 2, 3] (no dupes ā False), then print O(n) is faster.
def has_dup_fast(items):
seen = set()
for x in items:
if x in seen:
return True
seen.add(x)
return False
print(has_dup_fast([1, 2, 3]))
print("O(n) is faster")
š¬
Task 4: Free Play ā Count the Steps
Explore
Add a steps counter inside a loop to see Big-O in action. Try changing n from 5 to 50 ā one loop grows linearly, nested loops grow as nĀ². Watch the numbers!