Every algorithm built across this course so far has a Big O rating, binary search is O(log n), naive Fibonacci is O(2ⁿ), bubble sort is O(n²). This page makes precise what those labels actually mean, using nothing but real, verified numbers already produced by those exact algorithms.
Big O describes how the amount of work grows as the input size (n) grows, not the exact number of operations, and almost always the worst case.
Every curve below comes from an algorithm already built and verified elsewhere on this site, not an abstract formula. Toggle which ones are visible and watch how dramatically they separate as n grows.
n = 20
These aren't hypothetical examples. Every single row below is something you've already run, stepped through, and watched execute elsewhere in this course.
| Algorithm | Class | Where you've seen it |
|---|---|---|
| Array index access | O(1) | Constant time, regardless of array size |
| Binary search | O(log n) | Searching Algorithms lesson, halves the search space every step |
| Linear search | O(n) | Searching Algorithms lesson, worst case checks every element |
| Merge sort | O(n log n) | Sorting Algorithms lesson, barely changes between best and worst case |
| Quicksort (typical) | O(n log n) | Sorting Algorithms lesson, but see the exam tip below |
| Bubble sort / Insertion sort | O(n²) | Sorting Algorithms lesson, nested comparisons |
| Quicksort (worst case) | O(n²) | Genuinely happens on already-sorted input with a naive pivot, see the sorting lesson |
| Naive recursive Fibonacci | O(2ⁿ) | Recursion Fundamentals lesson, verified 2,692,537 calls for fib(30) |
Quicksort is deliberately listed twice: its typical performance is excellent, O(n log n), but with a naive pivot choice (always the last element), an already-sorted list is its actual worst case, O(n²), the opposite pattern from every other sort here. Same algorithm, two different classes, depending entirely on the input.
"Just drop the small stuff" sounds like a shortcut. Here's the actual reasoning, worked through with real numbers, not just asserted.
Four short pseudocode snippets. Work out each one's Big O before revealing the answer, verified against real operation counts, not just claimed.