• Measures how an algorithm slows down as input grows
• Only the worst case matters
• Constants get dropped, so \(100n\) is just \(O(n)\)
• Helps compare algorithms before writing any code

Ordered from best to worst:

\[O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)\]

• \(O(1)\): constant, no matter the input size
• \(O(\log n)\): slow growth, very efficient
• \(O(n)\): grows with input
• \(O(n^2)\): nested loops, gets slow fast
• \(O(2^n)\): doubles each step, unusable at scale

Check each element one by one until the target is found.

• Best case: \(O(1)\), target is first
• Worst case: \(O(n)\), target is last or missing

\[T(n) = n\]

Works on any list. Gets slow on large ones.

Requires a sorted list. Cuts the search space in half each step.

• Best case: \(O(1)\), target is the middle
• Worst case: \(O(\log_2 n)\)

\[T(n) = \log_2 n\]

On 1,000,000 elements: binary search takes ~20 steps, linear takes up to 1,000,000.

n = 1:1000
searchDf = data.frame(
  n     = rep(n, 2),
  steps = c(n, log2(n)),
  type  = rep(c("linear search", "binary search"), each=length(n))
)
ggplot(searchDf, aes(x=n, y=steps, color=type)) +
  geom_line(linewidth=1) +
  labs(x="input size (n)", y="steps", color="algorithm") +
  theme_minimal()

Two nested loops over different sized inputs. Total operations are n times m.

• A fast computer running a bad algorithm still loses
• Binary search on 1M items: ~20 steps
• Linear search on 1M items: up to 1,000,000 steps
• Knowing Big-O means you pick the right algorithm from the start