Chapter 04 — Speeding Up Your Code with Big O

Big O as a practical tool

Big O helps identify slow algorithms and decide when code should be optimized

Speeding up code

Improving an algorithm so it takes fewer steps as input grows

Bubble Sort

A sorting algorithm that compares neighboring values and swaps them if they are out of order

How Bubble Sort works

It repeatedly compares adjacent values and swaps them until the array is sorted

Comparison

Checking two values to see which should come first

Swap

Switching two values’ positions in an array

Pass-through

One full scan through part of the array during sorting

Why it is called Bubble Sort

Larger values gradually bubble up to the end of the array

Sorted flag

A boolean value used to track whether the array is fully sorted

Unsorted until index

The rightmost index that still needs to be checked during Bubble Sort

Bubble Sort stopping condition

The algorithm stops after a full pass-through with no swaps

Bubble Sort comparisons

Bubble Sort compares neighboring pairs of values

Bubble Sort swaps

Bubble Sort swaps neighboring values when they are out of order

Bubble Sort worst case

When the array is sorted in reverse order

Bubble Sort Big O

O(N²)

Why Bubble Sort is O(N²)

It makes many comparisons and swaps across multiple pass-throughs

O(N²)

Quadratic time; the number of steps grows roughly with N squared

Quadratic time

A slow growth pattern where doubling the input can create about four times the work

Nested loops

Loops inside other loops, often leading to O(N²)

Duplicate checking with nested loops

O(N²), because each value may be compared with every other value

Quadratic problem

A problem solved slowly because it compares many pairs of values

Linear solution

A faster solution that processes each item once

Faster duplicate checking

Track existing values in another structure to avoid comparing every pair

existingNumbers array

An extra array used to remember which numbers have already appeared

Time-space tradeoff

Using more memory to make an algorithm faster

O(N²) to O(N) improvement

Replacing nested comparisons with a single loop and extra storage

Main lesson of Chapter 04

Big O helps reveal slow O(N²) patterns and guides you toward faster solutio