Three ways a program lets you down

Until now your programs have lived in an ideal world: the input is always valid, the data is always clean, the size is always small.

The real world is not like that. Programs disappoint in three ways:

The three look unrelated but are one question wearing three hats: how do you know your program actually works?

---

1. Too slow: complexity

Why not just use a stopwatch

The obvious way to find out whether an algorithm is fast is to time it:

import time

def sum_to(n: int) -> int:
    total = 0
    for i in range(n):
        total += i
    return total

for n in [10_000, 100_000, 1_000_000]:
    t = time.time()
    sum_to(n)
    print(f"n = {n:>9,}  took {time.time() - t:.4f} s")

That number is useful, but it cannot compare algorithms, because it depends on the machine, what the CPU is doing at that moment, the Python version, and whether you have other programs open.

We need a measure that is independent of the machine.

Count steps, not seconds

Instead: count how many basic operations the algorithm performs. A basic operation is arithmetic, a comparison, an assignment, an index — anything that takes one step.

def sum_to(n):
    total = 0            # 1 step
    for i in range(n):   # n iterations
        total += i       # 1 step each
    return total         # 1 step

About n + 2 steps.

Another:

def has_duplicate(items):
    for i in range(len(items)):        # n times
        for j in range(len(items)):    # n times each
            if items[i] == items[j]:   # 1 step
                ...

That is n × n = n² steps.

The essential difference is how they grow as n increases.

Multiply n by ten and the first grows tenfold; the second grows a hundredfold.

Big-O notation

Since only the trend at large n matters:

• keep the fastest-growing term: n² + 3n + 5 → n²
• drop constant factors: 5n and 100n are both n

Written O(...):

• n + 2 → O(n), linear
• n² → O(n²), quadratic
• 3 → O(1), constant (independent of n)

Why can the constants go? Because once the order differs, no constant can compensate:

# O(n) with a huge constant vs O(n²) with a small one
for n in [10, 100, 1000, 10000]:
    linear = 100 * n
    quadratic = n * n
    winner = "O(n) wins" if linear < quadratic else "O(n²) wins"
    print(f"n={n:>6}  100n = {linear:>12,}   n² = {quadratic:>14,}   {winner}")

Past n = 100 the O(n) version never loses again. That is why the order matters more than the constant.

The common orders

Fastest to slowest:

import math
print(f"{'n':>8} {'log n':>8} {'n':>10} {'n log n':>12} {'n²':>14}")
for n in [10, 100, 1000, 10000, 100000]:
    print(f"{n:>8} {math.log2(n):>8.1f} {n:>10,} {n*math.log2(n):>12,.0f} {n*n:>14,}")

The complexity of Python’s operations

This table is worth memorizing:

This is behind L6’s claim that lists search slowly and sets search fast:

import time

n = 30_000
data_list = list(range(n))
data_set = set(data_list)

t = time.time()
for x in range(0, n, 100):
    x in data_list
list_time = time.time() - t

t = time.time()
for x in range(0, n, 100):
    x in data_set
set_time = time.time() - t

print(f"list in: {list_time:.4f} s")
print(f"set in:  {set_time:.6f} s")
print(f"the set is about {list_time / set_time:.0f}x faster")

import time

words = ["hello"] * 20_000

t = time.time()
s = ""
for w in words:
    s += w
concat_time = time.time() - t

t = time.time()
s2 = "".join(words)
join_time = time.time() - t

print(f"+= concatenation: {concat_time:.4f} s")
print(f"join:             {join_time:.6f} s")
print(f"same result: {s == s2}")

Why binary search is O(log n)

L7 wrote binary search and deferred the complexity to here.

Each comparison halves the range: n → n/2 → n/4 → … → 1.

The question is: how many halvings take n down to 1? That is log₂ n.

import math
for n in [100, 1_000, 1_000_000, 1_000_000_000]:
    print(f"{n:>15,} elements need at most {math.ceil(math.log2(n)):>2} comparisons")

A billion elements, thirty comparisons. That is what logarithmic complexity buys, and why sorted data is so valuable.

Memoization: exponential down to linear

L7 found that naive Fibonacci needs a quarter of a million calls, and promised a fix here.

The cause is the same subproblem being computed over and over. The remedy is direct: remember what you have already computed.

import time

def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


def fib_memo(n: int, cache: dict[int, int] | None = None) -> int:
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]              # already known
    if n <= 1:
        return n
    result = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    cache[n] = result                # remember it
    return result


t = time.time(); fib_naive(28); naive_t = time.time() - t
t = time.time(); fib_memo(28);  memo_t = time.time() - t

print(f"naive recursion fib(28): {naive_t:.4f} s")
print(f"memoized        fib(28): {memo_t:.6f} s")
print(f"about {naive_t / memo_t:.0f}x faster")
print(f"and memoized handles fib(200) = {fib_memo(200)}")

Complexity falls from O(2ⁿ) to O(n) — each n is computed once.

The standard library has a ready-made decorator (L14 explains what a decorator is):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))
print(fib.cache_info())

One line of @lru_cache turns exponential into linear.

Space complexity

The same notation describes memory.

# O(1) space: a few variables regardless of n
def sum_loop(n: int) -> int:
    total = 0
    for i in range(n):
        total += i
    return total

# O(n) space: builds a list of length n
def sum_list(n: int) -> int:
    return sum([i for i in range(n)])

print(sum_loop(1000), sum_list(1000))

L13 shows how generators bring O(n) space back down to O(1).

How to improve complexity

In order of effectiveness:

1. change the algorithm — O(n²) to O(n log n) is a change of order
2. change the data structure — list lookup to set lookup is O(n) to O(1)
3. avoid recomputation — memoization
4. use built-ins — sum(), sorted(), "".join() are implemented in C and run an order of magnitude faster than a Python loop

import time
n = 2_000_000

t = time.time()
total1 = 0
for i in range(n):
    total1 += i
loop_t = time.time() - t

t = time.time()
total2 = sum(range(n))
builtin_t = time.time() - t

print(f"hand-written loop: {loop_t:.4f} s")
print(f"built-in sum:      {builtin_t:.4f} s")
print(f"about {loop_t / builtin_t:.1f}x faster (both O(n); the difference is the constant)")

---

2. It crashes: exceptions

Syntactically valid, still fails

x = 10
y = 0
print(x / y)

That code is entirely valid and compiled without complaint, but failed at run time. An error that occurs during execution is an exception.

Left unhandled, it terminates the program — not one further line runs.

try / except

def safe_divide(a: float, b: float) -> float | None:
    try:
        return a / b
    except ZeroDivisionError:
        print("cannot divide by zero")
        return None

print(safe_divide(10, 2))
print(safe_divide(10, 0))
print("the program continues")

The try body runs normally; the moment an exception is raised, control jumps to the matching except.

Catch specific exceptions

def parse_age(text: str) -> int | None:
    try:
        return int(text)
    except ValueError:
        print(f"'{text}' is not an integer")
        return None

for s in ["18", "abc", "3.14", ""]:
    print(s, "→", parse_age(s))

This closes the loop from L3, where non-numeric input crashed the program and I said L11 would fix it.

Several except clauses

def get_item(data: dict[str, list[int]], key: str, index: int) -> int | None:
    try:
        return data[key][index]
    except KeyError:
        print(f"no key {key}")
    except IndexError:
        print(f"index {index} out of range")
    except TypeError as e:
        print(f"wrong type: {e}")
    return None

d = {"a": [1, 2, 3]}
print(get_item(d, "a", 1))
print(get_item(d, "b", 0))
print(get_item(d, "a", 10))

At most one clause runs — the first one, top to bottom, that matches.

else and finally

def divide(a: float, b: float) -> None:
    try:
        result = a / b
    except ZeroDivisionError:
        print("  failed")
    else:
        print(f"  succeeded, result {result}")     # only when nothing was raised
    finally:
        print("  cleanup")                          # always

print("10 / 2:"); divide(10, 2)
print("10 / 0:"); divide(10, 0)

• else runs when the try body raised nothing. Put “things to do only on success” here
• finally runs regardless. Put cleanup here — closing files, dropping connections

finally even beats return:

def f() -> str:
    try:
        return "returned from try"
    finally:
        print("  finally ran anyway")

print(f())

raise: throwing your own

def set_age(age: int) -> int:
    if age < 0:
        raise ValueError(f"age cannot be negative: {age}")
    if age > 150:
        raise ValueError(f"implausible age: {age}")
    return age

print(set_age(18))
print(set_age(-5))

When should you raise rather than return None?

When the caller must not be allowed to ignore the problem. A returned None is easy to overlook, and the error then surfaces far from its cause. An exception stops immediately, and the traceback points at where it went wrong.

Custom exceptions

class InsufficientFunds(Exception):
    """Not enough money in the account."""
    def __init__(self, balance: float, amount: float) -> None:
        super().__init__(f"balance {balance}, cannot withdraw {amount}")
        self.balance = balance
        self.amount = amount


def withdraw(balance: float, amount: float) -> float:
    if amount > balance:
        raise InsufficientFunds(balance, amount)
    return balance - amount


try:
    withdraw(100, 500)
except InsufficientFunds as e:
    print("caught:", e)
    print("short by:", e.amount - e.balance)

Custom exceptions inherit from Exception — L10’s inheritance earning its keep. The benefit is that a caller can catch precisely this failure rather than every ValueError.

with: automatic cleanup

# the manual version, easy to forget
f = open("/tmp/demo.txt", "w")
f.write("hello")
f.close()

# the with version, closed automatically
with open("/tmp/demo.txt", "w") as f:
    f.write("hello")
# closed by here, even if something was raised inside

with open("/tmp/demo.txt") as f:
    print(f.read())

with guarantees cleanup on exit — equivalent to a correctly written try...finally. Files in full are L12.

Check first, or apologize after

Two styles:

d = {"a": 1}

# style one: Look Before You Leap
if "b" in d:
    print(d["b"])
else:
    print("LBYL: no such key")

# style two: Easier to Ask Forgiveness than Permission
try:
    print(d["b"])
except KeyError:
    print("EAFP: no such key")

Python prefers the second (EAFP), because:

• the normal path costs nothing extra (exceptions only cost when raised)
• it avoids the race between checking and using
• the main line of the code stays clear, with failure handling to one side

But write the simple check when it is simple. if not items: return is far clearer than wrapping things in a try.

---

3. Quietly wrong: assertions and tests

assert: checking what you believe must hold

def average(nums: list[float]) -> float:
    assert len(nums) > 0, "average does not accept an empty list"
    return sum(nums) / len(nums)

print(average([1, 2, 3]))
print(average([]))

assert condition, message says: “I believe this must be true here. If it is not, my program has a bug — stop immediately.”

Assertions are not exception handling

The most-confused point in the lecture. Keep them apart:

print("__debug__ is:", __debug__)
print("This decides whether assert runs. True normally, False under -O.")

Assertions as executable documentation

def binary_search(sorted_nums: list[int], target: int) -> int:
    assert sorted_nums == sorted(sorted_nums), "the input must be sorted"
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        if sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7], 5))
print(binary_search([5, 3, 1], 3))

That assertion turns the precondition “the input must be sorted” into an executable check. Better than a comment — comments go stale, assertions do not.

pytest: making testing routine

L8 established that tests, not plausibility, decide whether code is correct. We hand-wrote a checking loop there. Here is the standard tool.

Install:

python3 -m pip install pytest

The rules are simple:

• files named test_*
• functions named test_*
• express expectations with assert

Given mymath.py:

# mymath.py
def add(a: int, b: int) -> int:
    return a + b

def divide(a: float, b: float) -> float:
    if b == 0:
        raise ValueError("cannot divide by zero")
    return a / b

the test file:

# test_mymath.py
import pytest
from mymath import add, divide


def test_add_positive():
    assert add(2, 3) == 5

def test_add_negative():
    assert add(-1, -1) == -2

def test_add_zero():
    assert add(0, 5) == 5

def test_divide_normal():
    assert divide(10, 2) == 5.0

def test_divide_by_zero():
    with pytest.raises(ValueError):      # we expect it to raise
        divide(10, 0)

Then:

python3 -m pytest              # run everything
python3 -m pytest -v           # name each test
python3 -m pytest -k divide    # only those matching "divide"

The output looks like:

test_mymath.py .....                        [100%]
======== 5 passed in 0.02s ========

and on failure pytest tells you which test, what was expected, and what happened:

E       assert 6 == 5
E        +  where 6 = add(2, 3)

We cannot run pytest inside these notes, but the core idea simulates fine:

def add(a: int, b: int) -> int:
    return a + b

def run_tests() -> None:
    cases = [
        ("positives",   lambda: add(2, 3), 5),
        ("negatives",   lambda: add(-1, -1), -2),
        ("with zero",   lambda: add(0, 5), 5),
        ("deliberately wrong", lambda: add(2, 3), 6),      # this one fails
    ]
    passed = 0
    for name, func, expected in cases:
        got = func()
        if got == expected:
            print(f"  ok   {name}")
            passed += 1
        else:
            print(f"  FAIL {name}: expected {expected}, got {got}")
    print(f"{passed}/{len(cases)} passed")

run_tests()

What to test

Recalling L8’s edge list, a function deserves at minimum:

• the normal case: typical input
• empty input: empty list, empty string
• a single element
• boundaries: zero, negatives, largest and smallest
• failure: does invalid input raise as it should

def clamp(x: float, lo: float, hi: float) -> float:
    """Constrain x to [lo, hi]."""
    if lo > hi:
        raise ValueError("lo must not exceed hi")
    return max(lo, min(x, hi))


checks = [
    ("inside the range", clamp(5, 0, 10), 5),
    ("below the floor",  clamp(-3, 0, 10), 0),
    ("above the ceiling", clamp(99, 0, 10), 10),
    ("exactly on the edge", clamp(0, 0, 10), 0),
    ("degenerate range", clamp(7, 3, 3), 3),
]
for name, got, expected in checks:
    print(f"  {'ok  ' if got == expected else 'FAIL'} {name}: {got}")

try:
    clamp(5, 10, 0)
    print("  FAIL invalid range did not raise")
except ValueError:
    print("  ok   invalid range raised ValueError")

Summary

Complexity

• Measure algorithms by counted basic operations, independent of the machine
• Big-O keeps the highest-order term and drops constants, because a different order always wins eventually
• The ladder: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
• Learn Python’s costs: in on a list is O(n); on a set or dict it is O(1)
• += on strings inside a loop is O(n²) — use join
• Memoization takes overlapping-subproblem recursion from O(2ⁿ) to O(n); @lru_cache does it in one line
• Built-ins are faster by a smaller constant and cannot rescue a bad algorithm. Fix the order first

Exceptions

• Valid code still fails at run time; that is an exception
• try / except SpecificType / else (nothing raised) / finally (always)
• Never write a bare except:
• raise throws your own; custom exceptions inherit from Exception
• with guarantees cleanup, equivalent to a well-written try...finally
• Python prefers EAFP over LBYL

Assertions and tests

• Exceptions handle expected external problems; assertions check impossible internal states
• Never catch AssertionError — a failed assertion should crash
• Assertions are skipped under -O, so they cannot validate user input
• pytest: test_-prefixed files and functions, assert for expectations, pytest.raises for failures
• The platform calls your function and compares the return value — so you must return
• Test at least: normal, empty, single, boundary, failure

Exercises

1. Give the time complexity of each and justify it:

   def f1(n): return sum(range(n))
   def f2(a): return [x for x in a if x in a]
   def f3(a): return sorted(set(a))
   def f4(n):
       count = 0
       i = n
       while i > 1:
           i = i // 2
           count += 1
       return count

2. Add memoization to your count_ways (coin combinations) from L7 and measure the speedup.
3. Write safe_int(text: str, default: int = 0) -> int, returning the default instead of crashing on failure.
4. What is wrong with this? Fix it:

   def process(filename):
       try:
           f = open(filename)
           data = f.read()
           return int(data)
       except:
           return 0

5. Write a pytest suite for the Stack class you built in Lab 9, covering at least: empty, one element, several elements, and popping an empty stack.
6. Add pre- and postconditions with assert to L7’s binary_search. (Hint: the postcondition can check that the returned index really holds the target, or that −1 was returned and the target really is absent.)
7. Measure it yourself: time 10,000 calls each of list.insert(0, x) and list.append(x) and confirm the O(n) versus O(1) difference.

The lab problems are in Lab 11.