Chapter 05 — Optimizing Code with and Without Big O

Big O limitation

Big O shows the general growth category, but not exact step counts

Same Big O different speed

Two algorithms can have the same Big O but different actual speeds

Selection Sort

A sorting algorithm that repeatedly finds the lowest value and moves it to the front of the unsorted section

How Selection Sort works

Find the lowest value in the unsorted section, then swap it with the first unsorted value

Selection Sort memory trick

Select the lowest remaining value

Lowest value

The smallest value found during a Selection Sort pass-through

Lowest value index

The index where the current lowest value is located

Selection Sort pass-through

One scan through the unsorted section to find the lowest value

Selection Sort swap

After finding the lowest value, swap it with the first value in the unsorted section

Selection Sort comparisons

Selection Sort compares values to find the lowest remaining value

Selection Sort swap pattern

Selection Sort makes at most one swap per pass-through

Selection Sort Big O

O(N²)

Why Selection Sort is O(N²)

It repeatedly scans the remaining unsorted values for each position

Bubble Sort vs Selection Sort

Both are O(N²), but Selection Sort usually performs fewer swaps

Why Selection Sort can be faster than Bubble Sort

Selection Sort usually swaps once per pass, while Bubble Sort may swap many times

Constant

A fixed number that Big O ignores

Ignoring constants

Big O removes fixed multipliers because it focuses on growth rate

What N² / 2 becomes

O(N²)

What 2N becomes

O(N)

What 100N becomes

O(N)

Big O category

A general speed classification based on how steps grow as input grows

Big O is best for

Comparing algorithms from different growth categories

When Big O is not enough

When two algorithms have the same Big O category

Practical example from Chapter 05

Two even-number printing algorithms are both O(N), but one is faster because it skips odd numbers

Significant steps

The meaningful operations inside an algorithm that contribute to total step count

Step counting

Counting actual operations to compare algorithms more precisely

Big O optimization

Improving the growth category of an algorithm

Non-Big O optimization

Making an algorithm faster without changing its Big O category

Main lesson of Chapter 05

Big O is powerful, but exact step counts still matter when algorithms share the same Big