Week 01 · 3 hours total

Big-O & Benchmarking
How Fast Is Your Code?

What makes one algorithm faster than another? This week you will learn Big-O notation to describe how code scales, and you will use Python's time module to actually measure it. You will run your first benchmarks, plot the results, and see growth curves come to life.

Active Week

Phase 1 · The Measuring Mindset — “Predict with Big-O, verify with benchmarks.”

Learning Objectives

📊Explain what Big-O notation means and why it matters for comparing algorithms

⏱Identify O(1), O(n), O(n²), and O(log n) growth patterns by counting operations

🔍Use Python's time module to measure execution time

📈Run benchmarks at different input sizes and plot results with matplotlib

⚖Understand trade-offs: time vs space, simplicity vs speed

💡Read a growth curve and match it to the correct Big-O class

This Week's Notebook

📓 Lecture Notebook

Week_01.ipynb

Big-O Notation, Timing & Your First Benchmark

⏱ ~3 hours · lecture + exercises + benchmark

What is an algorithm? What makes one "better"?
Big-O notation: O(1), O(n), O(n²), O(log n)
Counting operations and growth rate intuition
Measuring time with the time module
Benchmark demo: loop performance at different n values
Plotting results with matplotlib

▶ Open in Colab

Key Concepts: Quick Reference

Big-O Complexity Classes

# O(1) — Constant: does not depend on n
def get_first(lst):
    return lst[0]

# O(n) — Linear: grows with n
def find_max(lst):
    mx = lst[0]
    for x in lst:
        if x > mx:
            mx = x
    return mx

# O(n²) — Quadratic: nested loop
def all_pairs(lst):
    for a in lst:
        for b in lst:
            print(a, b)

Benchmarking with time

import time

sizes = [1000, 5000, 10000, 50000]
times = []

for n in sizes:
    data = list(range(n))
    start = time.time()
    find_max(data)
    elapsed = time.time() - start
    times.append(elapsed)

import matplotlib.pyplot as plt
plt.plot(sizes, times, 'o-')
plt.xlabel('Input Size (n)')
plt.ylabel('Time (seconds)')
plt.title('Linear Growth O(n)')
plt.show()

Exercises Overview

        L1 — Recall
        L2 — Apply
        L3 — Extend
      

L1 Classify Big-O

Given three functions (constant, linear, quadratic), identify the Big-O of each and explain your reasoning in a comment.

L1 Count Operations

Write a function with a nested loop. Count how many times the inner operation runs for n = 5, 10, 20. Predict the Big-O.

L2 Time It

Use time.time() to measure how long a sum-of-list loop takes for n = 1000, 10000, 100000. Print results.

L2 Plot a Curve

Benchmark a nested loop at sizes 100, 500, 1000, 2000. Plot the results and verify the O(n²) curve shape.

L3 Compare Two Approaches

Write two functions that solve the same problem (e.g., check for duplicates) with different Big-O. Benchmark both, plot on the same chart, and write a 3-sentence conclusion.

Big-O & BenchmarkingHow Fast Is Your Code?

Big-O & Benchmarking
How Fast Is Your Code?