Chapter 04 — Speeding Up Your Code with Big O

Bubble Sort

A sorting algorithm that compares adjacent values and swaps them if out of order

Adjacent comparison

Comparing two neighboring values

Swap

Switching two values’ positions

Pass-through

One scan through part of the array

Bubble Sort behavior

Larger values bubble toward the end of the array

Bubble Sort stopping condition

Stop after a full pass-through with no swaps

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; steps grow roughly with N squared

Nested loops

Loops inside loops, commonly causing O(N²)

Duplicate checking with nested loops

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

Time-space tradeoff

Using extra memory to make an algorithm faster

O(N²) to O(N) improvement

Replace pairwise comparisons with one loop plus extra storag