Phase 4: Computational Thinking & Algorithms · ~35 minutes · Python · uv

Big-O Intuition — Naming What You Just Saw

Quadruple the input and a quadratic algorithm doesn't get 4x slower. It gets 16x slower. That's not a guess — it's what actually happened when we measured it.

Hiring signal: Reasons about how code will behave at 100x the data, not just whether it works on the test case in front of them

What you will learn

Name growth patterns informally: constant, linear, logarithmic, quadratic
Derive Big-O intuition from measured timing data rather than memorized notation
Explain why 'it works on my test data' says nothing about whether it survives 100x the data
Predict which of two code snippets will slow down faster as input grows

Introduction

Type: Learn Languages: Python Prerequisites: Lesson 01 (Searching — Slow vs. Fast) Time: ~35 minutes

Objective

Learning objectives

Name growth patterns informally: constant, linear, logarithmic, quadratic
Derive Big-O intuition from measured timing data rather than memorized notation
Explain why "it works on my test data" says nothing about whether it survives 100x the data
Predict which of two code snippets will slow down faster as input grows

What you're building

A script (growth_comparison.py) that:

Reproduces this lesson's has_duplicates_nested vs. has_duplicates_set timing at n = 500, 2000, 8000, printing the ratio between them at each size
Writes one additional function pair of your own invention — one with a nested loop over the same data (quadratic), one without (linear or better) — solving any small real task (e.g., finding the maximum pairwise sum, or counting matching pairs)
Times your own pair at the same three sizes and prints whether the ratio grows the way this lesson predicts (roughly 16x from a 4x input increase, for quadratic)
Contains a comment identifying, in your own words, which of the four named growth patterns each of your two functions belongs to, and why

Function A processes a list with one single loop that does a constant amount of work per item. Function B processes the same list with a loop inside a loop, both over the full list. If the list size goes from 1,000 to 4,000 items (4x), what's the most accurate prediction?

This is exactly the has_duplicates_nested vs. has_duplicates_set measurement from this lesson, described abstractly. Function A (single loop, constant work per item) is linear — time scales directly with input, so 4x the data means roughly 4x the time. Function B (loop nested inside a loop, both over the full list) is quadratic — 4x the data means roughly 4² = 16x the time, which is precisely the 500→2000 and 2000→8000 pattern measured above. This prediction doesn't require running the code first; recognizing the shape (single pass vs. nested passes over the same data) is what lets you predict it in advance.

Unlock the full lesson

You've read the first 2 sections. The rest of this lesson covers The Problem, Check Yourself, Key Terms & Next — plus a hands-on lab, quiz, and project artifact.

Create a free account to unlock Phase 0 and Phase 1 of every course — no credit card.