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!
šļø Extra Practice ā Algorithm Reps
Big-O only clicks when you count the steps yourself, again and again. Every task below makes you measure real work instead of guessing.
ā”
Task 5: Constant Time O(1)
Easy
Write first_item(items) that returns items[0]. It does the same amount of work whether the list has 5 or 5 million things ā that is O(1). Print it for [9, 8, 7] and for list(range(1000000)).
Write count_steps(n) that loops n times, counting each loop in a steps variable, and returns the count. Print the steps for n = 10, 100 and 1000. Notice the steps grow exactly like n.
10
100
1000
def count_steps(n):
steps = 0
for i in range(n):
steps += 1
return steps
print(count_steps(10))
print(count_steps(100))
print(count_steps(1000))
š²
Task 7: Count the Steps of O(nĀ²)
Medium
Now write count_pairs(n) with a loop inside a loop, counting every inner step. Print it for n = 5, 10 and 100. Ten times bigger input, but a hundred times more work ā that is why O(nĀ²) hurts.
25
100
10000
def count_pairs(n):
steps = 0
for i in range(n):
for j in range(n):
steps += 1
return steps
print(count_pairs(5))
print(count_pairs(10))
print(count_pairs(100))
āļø
Task 8: Count the Steps of O(log n)
Tricky
Write halvings(n) that keeps halving n (using n = n // 2) until it reaches 0, counting each halving. Print it for 8, 1024 and 1000000. A million items in only about twenty steps! š¤Æ
4
11
20
def halvings(n):
steps = 0
while n > 0:
n = n // 2
steps += 1
return steps
print(halvings(8))
print(halvings(1024))
print(halvings(1000000))
š§®
Task 9: O(n) Loop vs O(1) Formula
Medium
Add up 1ā¦n two ways: sum_loop(n) with a loop, and sum_formula(n) using n * (n + 1) // 2. Print both for n = 1000 ā same answer, wildly different work.
500500
500500
def sum_loop(n):
total = 0
for i in range(1, n + 1):
total += i
return total
def sum_formula(n):
return n * (n + 1) // 2
print(sum_loop(1000))
print(sum_formula(1000))
š¢
Task 10: Boss Level: Slow List vs Fast Set
Boss
Searching a list is O(n); searching a set is about O(1). Write steps_in_list(items, target) that counts how many items it checks before finding the target. Print the steps for finding 9999 in list(range(10000)), then print 9999 in set(range(10000)) ā which needs no scan at all.
10000
True
def steps_in_list(items, target):
steps = 0
for item in items:
steps += 1
if item == target:
return steps
return steps
print(steps_in_list(list(range(10000)), 9999))
print(9999 in set(range(10000)))