Spot the Complexity: Learn Big O

Benchmark real Python code and visualize Big O growth curves.

Introduction

30 Second Summary

Ever wonder why some apps feel instant while others crawl as your data grows? In technical interviews, explaining this scaling behavior is one of the most commonly tested skills.

In this project, you will build a complexity benchmarking lab that times real Python functions, plots their growth curves with matplotlib, and proves visually how different algorithm complexities behave at scale.

What You'll Build

A Python script that benchmarks functions of increasing complexity, measures their execution time across growing input sizes, and generates visual comparison charts showing how each Big O class behaves in practice.

By the end of this project, you'll have:

  • A benchmarking utility that measures real execution time across growing input sizes using Python's performance counter.
  • Visual growth curve charts comparing O(1), O(n), O(n^2), O(log n), and O(n log n) complexity classes side by side.
  • A hash map optimization demonstration proving the single most common interview pattern for turning slow code into fast code.
  • Secret Mission: Analyze a realistic interview function end-to-end and deliver a professional complexity explanation.

Are there any prerequisites?

You need basic Python knowledge (variables, loops, and functions). No prior Big O or algorithm knowledge is required.

Set Up Your Project

Before you can benchmark algorithms, you need a working environment with the right tools. Python handles the timing logic, and matplotlib draws the growth-curve charts that make Big O intuition click.

In this step, you will verify Python is ready, install matplotlib, and create the project file that holds your benchmarking utility.

In this step, get ready to:
  • Confirm Python 3.14 is available in your terminal.
  • Install and verify matplotlib for charting.
  • Create the project file with the benchmarking utility function.
Verify your Python version

Your complexity lab relies on Python's time.perf_counter() for precise timing measurements. Let's confirm your Python installation is ready.

  • Open a terminal in VS Code by pressing Ctrl+` (backtick key, top-left of your keyboard).
  • Check your Python version by running this command:
python3 --version

You should see Python 3.14 followed by a patch number (e.g. 3.14.6).

Not seeing Python 3.14?

If you see "command not found", Python is not installed or not on your PATH. Download it from python.org/downloads.

On Windows, try python --version instead. The Python installer on Windows sometimes registers the command without the trailing 3.

Help me troubleshoot my Python installation.

Install matplotlib

Matplotlib is the Python library that draws charts and graphs. You will use it to plot growth curves that show how execution time scales with input size.

  • Install matplotlib by running this command:
pip3 install matplotlib==3.10.9

Why pin the version?

Adding ==3.10.9 tells pip to install that exact release. This ensures the chart output matches what you see in this project, even if a newer version comes out later.

  • Verify the installation succeeded by running:
python3 -c "import matplotlib; print(matplotlib.__version__)"

You should see 3.10.9 printed in your terminal.

Seeing a permission error or ModuleNotFoundError?

If pip says "permission denied", try adding --user to the end of the install command.

If the verify command says ModuleNotFoundError, make sure pip3 and python3 point to the same Python installation. Running pip3 --version shows which Python it is linked to.

Help me fix my matplotlib installation.

Create the project file with the benchmarking utility

Every benchmark in this project uses the same utility function to time code across different input sizes. You will write it once now and reuse it for the rest of the lab.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create your project folder and move into it by running these commands:
mkdir big-o-lab
cd big-o-lab
  • Confirm the folder exists by running:
ls

You should see big-o-lab listed if you run ls from the Desktop, or an empty output now that you are inside the new folder.

  • Open this folder in VS Code by running:
code .

What does code . do?

The code command launches VS Code from the terminal. The dot (.) means "open the current folder." VS Code will reopen with big-o-lab as its workspace.

  • In the VS Code Explorer sidebar on the left, click the new-file icon (a page with a small "+").
  • Name the file complexity_lab.py and press Enter.
  • Paste the following code into complexity_lab.py:
import time
import matplotlib.pyplot as plt


# --- Benchmarking utility ---

def benchmark(func, sizes, runs=3):
    """Time a function across different input sizes. Returns average times."""
    times = []
    for n in sizes:
        total = 0
        for _ in range(runs):
            data = list(range(n))
            start = time.perf_counter()
            func(data)
            end = time.perf_counter()
            total += end - start
        times.append(total / runs)
    return times

What does this code do?

The benchmark() function accepts any function and a list of input sizes, then times how long the function takes for each size.

  • time.perf_counter() captures high-resolution timestamps before and after each run.
  • list(range(n)) generates test data of size n outside the timing window so data creation does not skew results.
  • runs=3 repeats each measurement three times and averages the result to smooth out system noise.
  • Save complexity_lab.py by pressing Cmd+S (macOS) or Ctrl+S (Windows).

VS Code showing a yellow underline on the import?

If you see a warning under import matplotlib.pyplot, VS Code may be using a different Python interpreter than the one where you installed matplotlib.

Press Cmd+Shift+P (macOS) or Ctrl+Shift+P (Windows) to open the Command Palette, type "Python: Select Interpreter", and choose the Python 3.14 entry.

Help me fix the matplotlib import warning in VS Code.

✔️ Awesome, I've got everything!

Great. Double check you have saved complexity_lab.py before moving on.

ⓧ I'd like to double check the full code

Here is the complete complexity_lab.py at this point:

import time
import matplotlib.pyplot as plt


# --- Benchmarking utility ---

def benchmark(func, sizes, runs=3):
    """Time a function across different input sizes. Returns average times."""
    times = []
    for n in sizes:
        total = 0
        for _ in range(runs):
            data = list(range(n))
            start = time.perf_counter()
            func(data)
            end = time.perf_counter()
            total += end - start
        times.append(total / runs)
    return times

Your benchmarking lab is ready to go. Next up, you will write your first pair of functions and see how O(1) and O(n) behave when you put them on a chart.

Benchmark O(1) and O(n)

Your benchmarking utility is ready to measure any function you throw at it. Now it's time to write functions that showcase two fundamental complexity classes and see how they perform as input grows.

In this step, you'll write O(1) and O(n) functions, benchmark them across growing input sizes, and plot the results with matplotlib to see how their execution times compare visually.

In this step, get ready to:
  • Learn what Big O notation measures and how to spot O(1) vs O(n) in code.
  • Write constant-time and linear-time functions in Python.
  • Generate your first matplotlib chart comparing their growth curves.
Build the intuition: what Big O actually measures

Big O notation describes how execution time grows as input size increases. It doesn't tell you the exact runtime in seconds. It tells you the shape of the growth.

The key question to ask when reading any code: "How many times does the core operation run as n grows?"

What do O(1) and O(n) mean?

O(1) means "the same time no matter what." Whether you have 10 items or 10 million, the operation takes one step. Accessing an array element by index is O(1).

O(n) means "time grows proportionally with input." If you double the items, you double the work. Scanning every element in a list to sum them is O(n).

Write constant and linear time functions

Time to turn theory into code. You'll write two functions that your benchmark() utility will measure.

  • In complexity_lab.py, add this code below the benchmark() function:
# --- O(1): Constant time ---

def constant_time(data):
    """Access the first element. Always one operation regardless of size."""
    return data[0] if data else None

What does this code do?

This function accesses data[0], the first element of the list. Whether the list has 100 items or 100,000, accessing one index is always one operation.

That's what makes it O(1). The input size is irrelevant to the work performed.

  • Save complexity_lab.py.

You won't see any output yet. The next function adds the O(n) comparison.

  • Now add the linear time function directly below constant_time:
# --- O(n): Linear time ---

def linear_time(data):
    """Sum all elements. Touches every element once."""
    total = 0
    for item in data:
        total += item
    return total

What does this code do?

The for item in data loop visits every element exactly once. If the list has 5,000 items, the loop runs 5,000 times.

That's O(n). Double the input and you double the work. The signal in code is a single loop that touches every element.

  • Save complexity_lab.py.

No output yet. The plotting function in the next substep benchmarks both functions and generates a chart.

Seeing a red underline in VS Code?

Make sure each function is at the top level of the file (no extra indentation). Python functions start with def at column 1, not indented inside another block.

Help me fix a syntax error in my complexity_lab.py file.

Plot the first growth curve chart

Both functions are written. Now you'll add a plotting function that benchmarks them across seven input sizes and renders the results as a line chart.

  • Add the plotting function and main block below linear_time:
# --- Plotting ---

def plot_basic_complexities():
    """Plot O(1) and O(n) growth curves."""
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000]

    print("Benchmarking O(1)...")
    times_constant = benchmark(constant_time, sizes)

    print("Benchmarking O(n)...")
    times_linear = benchmark(linear_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_constant, "o-", label="O(1) - constant")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(1) vs O(n)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_basic.png")
    plt.show()
    print("Saved: plot_basic.png")


if __name__ == "__main__":
    plot_basic_complexities()

What does this code do?

  • sizes defines seven input sizes from 100 to 5,000. The benchmark utility runs each function at every size.
  • plt.plot() draws a line for each function's timing results. The format strings "o-" and "s-" give each line a different marker shape.
  • plt.savefig("plot_basic.png") saves the chart as an image file in your project folder.
  • if __name__ == "__main__" ensures the plotting runs only when you execute the script directly, not when it's imported.
  • Save complexity_lab.py.
  • Run the script by entering this command in your terminal:
python3 complexity_lab.py

A matplotlib window pops up with your first chart. The O(1) line stays nearly flat along the bottom, while the O(n) line rises steadily as input size grows.

After you close the chart window, check your big-o-lab folder. You should see a new file called plot_basic.png saved alongside your script.

Chart window not appearing?

  • Make sure you're running the script from inside the big-o-lab folder. Run cd ~/Desktop/big-o-lab first if you're not sure.
  • If you see a "ModuleNotFoundError" for matplotlib, confirm you installed it with pip3 install matplotlib==3.10.9 in the same Python environment you're running.
  • Check that your function names match exactly: constant_time and linear_time. A typo in the name means benchmark() can't find them.

Help me debug why my complexity_lab.py chart isn't showing up.

Why does O(1) stay flat?

The constant_time function always does one operation: grab the first element. It doesn't matter if the list has 100 items or 5,000. The work is identical every time.

The linear_time function, on the other hand, visits every element. More elements means more loop iterations, so the line climbs proportionally.

✔️ Awesome, I've got everything!

Great. Make sure you've saved complexity_lab.py and that plot_basic.png exists in your folder.

ⓧ I'd like to double check the full code

Here's the complete complexity_lab.py at this point:

import time
import matplotlib.pyplot as plt


# --- Benchmarking utility ---

def benchmark(func, sizes, runs=3):
    """Time a function across different input sizes. Returns average times."""
    times = []
    for n in sizes:
        total = 0
        for _ in range(runs):
            data = list(range(n))
            start = time.perf_counter()
            func(data)
            end = time.perf_counter()
            total += end - start
        times.append(total / runs)
    return times


# --- O(1): Constant time ---

def constant_time(data):
    """Access the first element. Always one operation regardless of size."""
    return data[0] if data else None


# --- O(n): Linear time ---

def linear_time(data):
    """Sum all elements. Touches every element once."""
    total = 0
    for item in data:
        total += item
    return total


# --- Plotting ---

def plot_basic_complexities():
    """Plot O(1) and O(n) growth curves."""
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000]

    print("Benchmarking O(1)...")
    times_constant = benchmark(constant_time, sizes)

    print("Benchmarking O(n)...")
    times_linear = benchmark(linear_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_constant, "o-", label="O(1) - constant")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(1) vs O(n)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_basic.png")
    plt.show()
    print("Saved: plot_basic.png")


if __name__ == "__main__":
    plot_basic_complexities()

You've just proved with real data that constant time means constant time. No matter how big the input gets, O(1) doesn't care. Next up, you'll add the function that makes interviewers nervous: O(n^2), the nested loop trap.

Add O(n²) — The Nested Loop Trap

Your chart from the last step tells a clear story: O(1) stays flat and O(n) rises in a straight line. But the most infamous complexity class in interviews makes both of those look tiny.

In this step, you'll add O(n²) to the chart. This is the complexity that turns a half-second operation into a five-minute one, and recognizing the code pattern that causes it is one of the most valuable interview skills you can build.

In this step, get ready to:
  • Understand why nested loops multiply rather than add.
  • Write a quadratic time function with nested loops.
  • Regenerate the growth curve chart showing all three complexities together.
Build the intuition: why nesting multiplies

A single loop that scans every element is O(n). But what happens when you put a loop inside another loop?

The outer loop runs n times. For each of those n iterations, the inner loop also runs n times. That gives you n × n = n² total operations.

The critical interview distinction

Two sequential loops (one after the other) are O(n) + O(n) = O(n). The total work is still proportional to n.

Two nested loops (one inside the other) are O(n × n) = O(n²). The total work is proportional to n squared. Many beginners incorrectly assume "two loops = O(n²)" but what matters is whether the loops are nested or sequential.

Write the quadratic time function

Your new function will use the classic nested loop pattern: for each element, scan all elements.

  • In complexity_lab.py, find the # --- Plotting --- comment.
  • Add the following function directly above that comment:
# --- O(n^2): Quadratic time ---

def quadratic_time(data):
    """Check all pairs. For each element, scan all elements."""
    count = 0
    for i in range(len(data)):
        for j in range(len(data)):
            count += 1
    return count

What does this code do?

The outer for i loop visits every element. For each visit, the inner for j loop visits every element again. With 5000 elements, that is 25 million operations.

This is the pattern behind "check all pairs" problems. The function does not do useful work here. It just counts iterations so you can measure the time cost of nesting.

  • Save complexity_lab.py.

You won't see a change yet. The next chunk wires this function into the chart.

Update the chart with all three curves

Now you need to tell the plotting function to benchmark and display the new O(n²) function alongside O(1) and O(n).

  • In complexity_lab.py, find the existing plot_basic_complexities() function and replace the entire function with this updated version:
def plot_basic_complexities():
    """Plot O(1), O(n), and O(n^2) growth curves."""
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000]

    print("Benchmarking O(1)...")
    times_constant = benchmark(constant_time, sizes)

    print("Benchmarking O(n)...")
    times_linear = benchmark(linear_time, sizes)

    print("Benchmarking O(n^2)...")
    times_quadratic = benchmark(quadratic_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_constant, "o-", label="O(1) - constant")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear")
    plt.plot(sizes, times_quadratic, "^-", label="O(n^2) - quadratic")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(1) vs O(n) vs O(n^2)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_basic.png")
    plt.show()
    print("Saved: plot_basic.png")

What changed?

Three additions make O(n²) appear on the chart. The benchmark(quadratic_time, sizes) call measures execution time across growing input sizes.

The new plt.plot line draws the O(n²) curve with a triangle marker ("^-"). The chart title is updated to reflect all three complexity classes.

  • Now find the if __name__ == "__main__": block at the bottom of the file and replace it with this updated version:
if __name__ == "__main__":
    print("=" * 50)
    print("BIG O COMPLEXITY LAB")
    print("=" * 50)

    print("\n--- Part 1: Basic Complexities ---")
    plot_basic_complexities()

    print("\nDone! Check the generated plots.")

What does this code do?

This adds a banner header and a section label so you can clearly see which part of the lab is running in the terminal output. As you add more plotting functions in later steps, each will get its own section label.

  • Save complexity_lab.py.
  • Run the script by entering this command in your terminal:
python3 complexity_lab.py
  • A chart window opens. You should see three curves: O(1) as a flat line at the bottom, O(n) as a gentle slope, and O(n²) as a steep curve that dwarfs the other two.
  • Close the chart window. Confirm that plot_basic.png has been regenerated in your big-o-lab folder.

Chart not showing O(n²)?

Make sure you replaced the entire plot_basic_complexities() function, including the docstring on the first line. If you only added lines inside the old function, the chart title and labels might be mismatched.

Check that quadratic_time is defined above the # --- Plotting --- comment. Python reads top to bottom, so the function must exist before the plotting code calls it.

Still stuck? Why isn't my O(n^2) curve showing up on the chart?

Why does O(n²) dominate so dramatically?

At n=5000, the O(n) function does 5,000 operations. The O(n²) function does 25,000,000. That 5,000x difference is exactly why interviewers care about recognizing nested loops. A solution that works fine on 100 items can grind to a halt on real data.

✔️ Awesome, I've got everything!

Great. Double check you have saved your file before moving on.

ⓧ I'd like to double check the full code

Here is the complete complexity_lab.py at this point:

import time
import matplotlib.pyplot as plt


# --- Benchmarking utility ---

def benchmark(func, sizes, runs=3):
    """Time a function across different input sizes. Returns average times."""
    times = []
    for n in sizes:
        total = 0
        for _ in range(runs):
            data = list(range(n))
            start = time.perf_counter()
            func(data)
            end = time.perf_counter()
            total += end - start
        times.append(total / runs)
    return times


# --- O(1): Constant time ---

def constant_time(data):
    """Access the first element. Always one operation regardless of size."""
    return data[0] if data else None


# --- O(n): Linear time ---

def linear_time(data):
    """Sum all elements. Touches every element once."""
    total = 0
    for item in data:
        total += item
    return total


# --- O(n^2): Quadratic time ---

def quadratic_time(data):
    """Check all pairs. For each element, scan all elements."""
    count = 0
    for i in range(len(data)):
        for j in range(len(data)):
            count += 1
    return count


# --- Plotting ---

def plot_basic_complexities():
    """Plot O(1), O(n), and O(n^2) growth curves."""
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000]

    print("Benchmarking O(1)...")
    times_constant = benchmark(constant_time, sizes)

    print("Benchmarking O(n)...")
    times_linear = benchmark(linear_time, sizes)

    print("Benchmarking O(n^2)...")
    times_quadratic = benchmark(quadratic_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_constant, "o-", label="O(1) - constant")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear")
    plt.plot(sizes, times_quadratic, "^-", label="O(n^2) - quadratic")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(1) vs O(n) vs O(n^2)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_basic.png")
    plt.show()
    print("Saved: plot_basic.png")


if __name__ == "__main__":
    print("=" * 50)
    print("BIG O COMPLEXITY LAB")
    print("=" * 50)

    print("\n--- Part 1: Basic Complexities ---")
    plot_basic_complexities()

    print("\nDone! Check the generated plots.")

You have now seen the explosive growth of O(n²) with your own eyes. Next, you will explore the opposite end of the spectrum: O(log n), the complexity class that barely grows at all, even with massive inputs.

Benchmark O(log n) and O(n log n)

In the last step, you saw how O(n^2) explodes off the chart compared to O(n). But not all algorithms are slower as they scale.

Some algorithms get faster at finding answers by cutting the search space in half at every step. In this step, you'll benchmark two new complexity classes that demonstrate this halving pattern: O(log n) and O(n log n).

In this step, get ready to:
  • Write a logarithmic binary search function and a linearithmic sorting function.
  • Benchmark both functions across input sizes up to 100,000.
  • Generate a chart proving O(log n) barely rises even at massive input sizes.
Build the intuition: the halving pattern

O(log n) means "cut the problem in half at every step." The classic example is binary search. Instead of scanning every element, you jump to the middle, check which half your answer could be in, and throw away the other half entirely.

The signal in code: any loop where the tracking variable doubles or halves each iteration. If you see left = mid + 1 or i *= 2, you're looking at O(log n).

What about O(n log n)?

O(n log n) means "do an O(log n) operation for each of n elements." This is how sorting algorithms work. Python's built-in sorted() uses Timsort, which is O(n log n) in the worst case.

Rule of thumb for interviews: if the input must be sorted first, your solution starts at O(n log n) minimum.

Why is this different from O(n)?

An O(n) algorithm touches every element once. An O(log n) algorithm skips most elements entirely. Searching 100,000 items takes about 17 steps with binary search, not 100,000.

Write logarithmic and linearithmic functions

Now you'll write two functions that demonstrate these complexity classes. The first performs a binary search (O(log n)). The second simply calls Python's sorted() (O(n log n)).

  • In complexity_lab.py, find the # --- Plotting --- comment.
  • Add both of these functions above that comment:
# --- O(log n): Logarithmic time ---

def logarithmic_time(data):
    """Binary search for the last element (worst case)."""
    left, right = 0, len(data) - 1
    target = data[-1]
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


# --- O(n log n): Linearithmic time ---

def linearithmic_time(data):
    """Sort the data. Python's built-in sort is O(n log n)."""
    return sorted(data)

What does this code do?

logarithmic_time() performs a binary search for the last element in the list. Searching for the last element guarantees worst-case behavior (the search always runs to completion), making benchmarks consistent.

linearithmic_time() calls Python's sorted(), which uses Timsort under the hood. Even though it's a single line of code, sorting n elements always costs O(n log n) work internally.

  • Save complexity_lab.py.

You won't see a change yet. The next chunk wires these functions into a chart.

Seeing a red underline in VS Code?

Make sure both functions are placed above the # --- Plotting --- comment and below the quadratic_time function. Check that the indentation uses consistent spaces (no mix of tabs and spaces).

Help me debug a red underline in my complexity_lab.py file

Plot the logarithmic chart

Time to visualize how these new complexity classes compare. You'll write a plotting function that benchmarks O(log n), O(n), and O(n log n) across much larger input sizes to make the differences clear.

  • In complexity_lab.py, find the plot_basic_complexities() function.
  • Add this new plotting function directly below it:
def plot_log_complexities():
    """Plot O(log n) and O(n log n) growth curves."""
    sizes = [100, 500, 1000, 5000, 10000, 50000, 100000]

    print("Benchmarking O(log n)...")
    times_log = benchmark(logarithmic_time, sizes)

    print("Benchmarking O(n log n)...")
    times_nlogn = benchmark(linearithmic_time, sizes)

    print("Benchmarking O(n) for comparison...")
    times_linear = benchmark(linear_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_log, "o-", label="O(log n) - binary search")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear scan")
    plt.plot(sizes, times_nlogn, "^-", label="O(n log n) - sort")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(log n) vs O(n) vs O(n log n)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_logarithmic.png")
    plt.show()
    print("Saved: plot_logarithmic.png")

What does this code do?

  • sizes goes up to 100,000 this time. Logarithmic functions handle large inputs so easily that you need bigger numbers to see any difference at all.
  • The function benchmarks O(log n), O(n log n), and O(n) for comparison. Including linear_time as a reference line helps you see where O(n log n) sits relative to something familiar.
  • The chart saves to plot_logarithmic.png so you can compare it side-by-side with your earlier chart.

Now you need to call this new function from the main block so it runs when you execute the script.

  • Scroll to the bottom of the file and find this line inside the if __name__ == "__main__": block:
    print("\nDone! Check the generated plots.")
  • Add these two lines directly above it:
    print("\n--- Part 2: Logarithmic Complexities ---")
    plot_log_complexities()
  • Save complexity_lab.py.
  • Run the script by entering this command in your terminal:
python3 complexity_lab.py
  • You should see two matplotlib chart windows appear. The second chart (plot_logarithmic.png) shows O(log n) as a nearly flat line even at n=100,000, O(n) rising steadily, and O(n log n) just slightly above O(n).

Chart not showing or script errors?

  • If you see a NameError mentioning logarithmic_time or linearithmic_time, make sure you placed those functions above the # --- Plotting --- section so Python can find them.
  • If the chart window appears blank, close it and re-run the script. Some systems need you to close the first chart window before the second one renders.
  • Make sure your terminal is inside the big-o-lab folder. Run ls to confirm you see complexity_lab.py listed.

Help me debug why my logarithmic chart isn't working

✔️ Awesome, I've got everything!

Great. Double check you've saved your file and that plot_logarithmic.png exists in your big-o-lab folder.

ⓧ I'd like to double check the full code

Here's the complete complexity_lab.py at this point. Compare it against yours:

import time
import matplotlib.pyplot as plt


# --- Benchmarking utility ---

def benchmark(func, sizes, runs=3):
    """Time a function across different input sizes. Returns average times."""
    times = []
    for n in sizes:
        total = 0
        for _ in range(runs):
            data = list(range(n))
            start = time.perf_counter()
            func(data)
            end = time.perf_counter()
            total += end - start
        times.append(total / runs)
    return times


# --- O(1): Constant time ---

def constant_time(data):
    """Access the first element. Always one operation regardless of size."""
    return data[0] if data else None


# --- O(n): Linear time ---

def linear_time(data):
    """Sum all elements. Touches every element once."""
    total = 0
    for item in data:
        total += item
    return total


# --- O(n^2): Quadratic time ---

def quadratic_time(data):
    """Check all pairs. For each element, scan all elements."""
    count = 0
    for i in range(len(data)):
        for j in range(len(data)):
            count += 1
    return count


# --- O(log n): Logarithmic time ---

def logarithmic_time(data):
    """Binary search for the last element (worst case)."""
    left, right = 0, len(data) - 1
    target = data[-1]
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


# --- O(n log n): Linearithmic time ---

def linearithmic_time(data):
    """Sort the data. Python's built-in sort is O(n log n)."""
    return sorted(data)


# --- Plotting ---

def plot_basic_complexities():
    """Plot O(1), O(n), and O(n^2) growth curves."""
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000]

    print("Benchmarking O(1)...")
    times_constant = benchmark(constant_time, sizes)

    print("Benchmarking O(n)...")
    times_linear = benchmark(linear_time, sizes)

    print("Benchmarking O(n^2)...")
    times_quadratic = benchmark(quadratic_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_constant, "o-", label="O(1) - constant")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear")
    plt.plot(sizes, times_quadratic, "^-", label="O(n^2) - quadratic")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(1) vs O(n) vs O(n^2)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_basic.png")
    plt.show()
    print("Saved: plot_basic.png")


def plot_log_complexities():
    """Plot O(log n) and O(n log n) growth curves."""
    sizes = [100, 500, 1000, 5000, 10000, 50000, 100000]

    print("Benchmarking O(log n)...")
    times_log = benchmark(logarithmic_time, sizes)

    print("Benchmarking O(n log n)...")
    times_nlogn = benchmark(linearithmic_time, sizes)

    print("Benchmarking O(n) for comparison...")
    times_linear = benchmark(linear_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_log, "o-", label="O(log n) - binary search")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear scan")
    plt.plot(sizes, times_nlogn, "^-", label="O(n log n) - sort")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(log n) vs O(n) vs O(n log n)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_logarithmic.png")
    plt.show()
    print("Saved: plot_logarithmic.png")


if __name__ == "__main__":
    print("=" * 50)
    print("BIG O COMPLEXITY LAB")
    print("=" * 50)

    print("\n--- Part 1: Basic Complexities ---")
    plot_basic_complexities()

    print("\n--- Part 2: Logarithmic Complexities ---")
    plot_log_complexities()

    print("\nDone! Check the generated plots.")

What should the chart look like?

The O(log n) line should be nearly invisible at the bottom of the chart. Even at n=100,000, binary search completes so fast that the line barely rises above zero.

The O(n) line rises steadily in the middle. The O(n log n) line sits just slightly above O(n). In interviews, this is why sorting is considered "good enough" for most problems. It's only marginally slower than linear.

Your chart now proves something powerful: O(log n) is essentially free at any realistic input size. Next up, you'll use this insight to tackle the single most common interview optimization pattern.

Apply the Hash Map Optimization

Your charts have proven that logarithmic algorithms barely break a sweat, even at 100,000 elements. Now it's time to learn the single most common optimization pattern tested in technical interviews.

The pattern is simple: replace a nested loop with a hash map lookup. Instead of scanning the entire array for each element (O(n^2)), you store what you have already seen in a dictionary and check it in O(1) time. This single trick drops many interview problems from quadratic to linear.

In this step, get ready to:
  • Write the brute force and hash map versions of the Two Sum problem.
  • Benchmark both solutions side by side across growing input sizes.
  • Generate a chart proving the hash map version stays flat while brute force explodes.
Understand the space-for-time trade-off

Many interview problems follow the same shape: "For each element, find something else in the array." The brute force approach checks every other element, giving you a nested loop and O(n^2) time.

The optimization is to store what you have already seen in a dictionary. Since Python dictionary lookups are O(1) on average, you only need one pass through the data.

Why a hash map instead of a second loop?

A nested loop asks: "For this element, scan the whole array to find its partner." That scan is the expensive part.

A hash map flips the question: "Have I already seen the partner I need?" Checking the map is O(1), so the total work drops from n * n operations to just n operations. You trade a small amount of memory (the dictionary) for a massive speed improvement.

Write the brute force and hash map functions

Both functions solve the same problem: find two numbers in the array that add up to a target value. The difference is how they search.

  • In complexity_lab.py, find the linearithmic_time function.
  • Add the following brute force function below it, above the # --- Plotting --- comment:
# --- O(n^2) brute force: Two Sum ---

def two_sum_brute(data):
    """Find two numbers that sum to a target. Check all pairs."""
    target = data[-1] + data[-2]
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] + data[j] == target:
                return (i, j)
    return None

What does this code do?

  • target = data[-1] + data[-2] picks a target sum we know exists in the data (the last two elements always add up to it).
  • The nested for i / for j loops check every possible pair. That's O(n^2) operations.
  • As soon as a match is found, the function returns the indices. If no match exists, it returns None.
  • Now add the optimized hash map version directly below two_sum_brute, still above # --- Plotting ---:
# --- O(n) optimized: Two Sum with hash map ---

def two_sum_hash(data):
    """Find two numbers that sum to a target. Use a dictionary."""
    target = data[-1] + data[-2]
    seen = {}
    for i, num in enumerate(data):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None

What does this code do?

  • seen = {} creates a dictionary that stores numbers we have already visited and their indices.
  • complement = target - num calculates what number we need to find to complete the pair.
  • if complement in seen checks the dictionary in O(1) time instead of scanning the whole array.
  • One pass through the data, one dictionary lookup per element. Total: O(n).
  • Save complexity_lab.py.

Seeing a red underline on two_sum_hash?

Make sure the function is placed between the linearithmic_time function and the # --- Plotting --- comment. Check that the indentation uses spaces, not tabs.

help me fix a syntax error in my Two Sum functions

Plot the optimization comparison

Now you will benchmark both solutions head-to-head and generate a chart that makes the difference undeniable.

  • In complexity_lab.py, find the plot_log_complexities function.
  • Add the following function below it, above the if __name__ == "__main__": block:
def plot_hash_optimization():
    """Plot O(n^2) brute force vs O(n) hash map for Two Sum."""
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000]

    print("Benchmarking Two Sum brute force O(n^2)...")
    times_brute = benchmark(two_sum_brute, sizes)

    print("Benchmarking Two Sum hash map O(n)...")
    times_hash = benchmark(two_sum_hash, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_brute, "o-", label="Brute force O(n^2)")
    plt.plot(sizes, times_hash, "s-", label="Hash map O(n)")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("The Hash Map Trick: O(n^2) vs O(n)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_hash_optimization.png")
    plt.show()
    print("Saved: plot_hash_optimization.png")

What does this code do?

  • It benchmarks both two_sum_brute and two_sum_hash across the same input sizes (100 to 5,000).
  • It plots both timing curves on the same chart so you can visually compare the growth rates.
  • It saves the result as plot_hash_optimization.png in your project folder.

The plotting function is ready, but the __main__ block does not call it yet.

  • Scroll down to the if __name__ == "__main__": block.
  • Find this line:
    print("\nDone! Check the generated plots.")
  • Add the following two lines directly above it:
    print("\n--- Part 3: Hash Map Optimization ---")
    plot_hash_optimization()
  • Save complexity_lab.py.
  • Run the script in your terminal by running this command:
python3 complexity_lab.py

You should see three chart windows appear one at a time (close each to proceed). The third chart shows the brute force line curving sharply upward while the hash map line stays nearly flat.

Chart window not appearing?

If the script hangs or no window appears, your matplotlib backend may not support interactive display. The PNG files are still saved to your big-o-lab folder. Open plot_hash_optimization.png directly to see the chart.

help me fix matplotlib not displaying charts

✔️ Awesome, I've got everything!

Great. Double check you have saved complexity_lab.py and all three PNG files exist in your big-o-lab folder.

ⓧ I'd like to double check the full code

import time
import matplotlib.pyplot as plt


# --- Benchmarking utility ---

def benchmark(func, sizes, runs=3):
    """Time a function across different input sizes. Returns average times."""
    times = []
    for n in sizes:
        total = 0
        for _ in range(runs):
            data = list(range(n))
            start = time.perf_counter()
            func(data)
            end = time.perf_counter()
            total += end - start
        times.append(total / runs)
    return times


# --- O(1): Constant time ---

def constant_time(data):
    """Access the first element. Always one operation regardless of size."""
    return data[0] if data else None


# --- O(n): Linear time ---

def linear_time(data):
    """Sum all elements. Touches every element once."""
    total = 0
    for item in data:
        total += item
    return total


# --- O(n^2): Quadratic time ---

def quadratic_time(data):
    """Check all pairs. For each element, scan all elements."""
    count = 0
    for i in range(len(data)):
        for j in range(len(data)):
            count += 1
    return count


# --- O(log n): Logarithmic time ---

def logarithmic_time(data):
    """Binary search for the last element (worst case)."""
    left, right = 0, len(data) - 1
    target = data[-1]
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


# --- O(n log n): Linearithmic time ---

def linearithmic_time(data):
    """Sort the data. Python's built-in sort is O(n log n)."""
    return sorted(data)


# --- O(n^2) brute force: Two Sum ---

def two_sum_brute(data):
    """Find two numbers that sum to a target. Check all pairs."""
    target = data[-1] + data[-2]
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] + data[j] == target:
                return (i, j)
    return None


# --- O(n) optimized: Two Sum with hash map ---

def two_sum_hash(data):
    """Find two numbers that sum to a target. Use a dictionary."""
    target = data[-1] + data[-2]
    seen = {}
    for i, num in enumerate(data):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None


# --- Plotting ---

def plot_basic_complexities():
    """Plot O(1), O(n), and O(n^2) growth curves."""
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000]

    print("Benchmarking O(1)...")
    times_constant = benchmark(constant_time, sizes)

    print("Benchmarking O(n)...")
    times_linear = benchmark(linear_time, sizes)

    print("Benchmarking O(n^2)...")
    times_quadratic = benchmark(quadratic_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_constant, "o-", label="O(1) - constant")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear")
    plt.plot(sizes, times_quadratic, "^-", label="O(n^2) - quadratic")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(1) vs O(n) vs O(n^2)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_basic.png")
    plt.show()
    print("Saved: plot_basic.png")


def plot_log_complexities():
    """Plot O(log n) and O(n log n) growth curves."""
    sizes = [100, 500, 1000, 5000, 10000, 50000, 100000]

    print("Benchmarking O(log n)...")
    times_log = benchmark(logarithmic_time, sizes)

    print("Benchmarking O(n log n)...")
    times_nlogn = benchmark(linearithmic_time, sizes)

    print("Benchmarking O(n) for comparison...")
    times_linear = benchmark(linear_time, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_log, "o-", label="O(log n) - binary search")
    plt.plot(sizes, times_linear, "s-", label="O(n) - linear scan")
    plt.plot(sizes, times_nlogn, "^-", label="O(n log n) - sort")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("Big O Growth Curves: O(log n) vs O(n) vs O(n log n)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_logarithmic.png")
    plt.show()
    print("Saved: plot_logarithmic.png")


def plot_hash_optimization():
    """Plot O(n^2) brute force vs O(n) hash map for Two Sum."""
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000]

    print("Benchmarking Two Sum brute force O(n^2)...")
    times_brute = benchmark(two_sum_brute, sizes)

    print("Benchmarking Two Sum hash map O(n)...")
    times_hash = benchmark(two_sum_hash, sizes)

    plt.figure(figsize=(10, 6))
    plt.plot(sizes, times_brute, "o-", label="Brute force O(n^2)")
    plt.plot(sizes, times_hash, "s-", label="Hash map O(n)")
    plt.xlabel("Input Size (n)")
    plt.ylabel("Time (seconds)")
    plt.title("The Hash Map Trick: O(n^2) vs O(n)")
    plt.legend()
    plt.grid(True)
    plt.tight_layout()
    plt.savefig("plot_hash_optimization.png")
    plt.show()
    print("Saved: plot_hash_optimization.png")


if __name__ == "__main__":
    print("=" * 50)
    print("BIG O COMPLEXITY LAB")
    print("=" * 50)

    print("\n--- Part 1: Basic Complexities ---")
    plot_basic_complexities()

    print("\n--- Part 2: Logarithmic Complexities ---")
    plot_log_complexities()

    print("\n--- Part 3: Hash Map Optimization ---")
    plot_hash_optimization()

    print("\nDone! Check the generated plots.")

You have now proven the most important interview optimization with real data. Next up: the Secret Mission challenges you to analyze a multi-pattern function and deliver a professional complexity explanation.

Secret mission

The Interview Talk Track

You can spot complexity classes in isolated functions. But real interview questions combine multiple patterns in a single solution. Can you analyze a multi-part function, identify the dominant operation, and deliver a structured explanation that would impress an interviewer?

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your resources for future interview prep, or delete them entirely.

Resources you used:

  • The big-o-lab folder containing complexity_lab.py.
  • Four generated PNG chart files (plot_basic.png, plot_logarithmic.png, plot_hash_optimization.png, plot_interview.png).
  • The matplotlib Python package installed via pip.

Keep everything running

No action needed. Choose this if you want to keep the lab as a personal reference for interview prep.

  • Your big-o-lab folder stays on your Desktop with all charts and code intact.
  • The matplotlib package remains installed and available for other Python projects.
  • You can rerun python3 complexity_lab.py any time to regenerate the charts or experiment with new functions.

Pause - I'll come back to this later

Since this is a local project with no running processes, there is nothing to pause. Your files sit quietly on disk until you return.

  • Close the complexity_lab.py file in VS Code to free up your editor tabs.
  • Your big-o-lab folder and all generated charts remain on your Desktop whenever you are ready to come back.

Delete - I don't want to use this again

Remove all project files and the installed package to start fresh.

  • Delete the project folder by running this command in Terminal:
rm -rf ~/Desktop/big-o-lab
  • Uninstall matplotlib by running:
pip3 uninstall matplotlib -y
  • On Windows, replace the first command with:
rmdir /s /q %USERPROFILE%\Desktop\big-o-lab

That's a Wrap!

That's a Wrap!

Nice work! You just built a complexity benchmarking lab that turns Big O from abstract textbook theory into measurable, visual reality.

You learned how to:

  • Build a benchmarking utility that measures real execution time using time.perf_counter() and proves how different complexity classes behave at scale.
  • Visualize O(1), O(n), O(n^2), O(log n), and O(n log n) growth curves with matplotlib, turning abstract notation into charts you can point at.
  • Demonstrate the hash map optimization pattern, the single most common interview technique for dropping O(n^2) to O(n).
  • Secret Mission: Analyzed a multi-pattern interview function and delivered a structured complexity explanation using the professional talk track template.

Ready to quiz yourself?