Why Big-O Does Not Predict Every Run
This planned lesson starts with two correct ways to search a sorted array: a scan and binary search. An animation shows the scan's neighboring memory accesses beside binary search's shrinking interval and jumping probes. The narration distinguishes the comparison count from elapsed time, then explains how input size, cache locality, branch behavior, and implementation constants affect a real run.
The demonstration plots repeated measurements for increasing arrays and labels the graph as an example workload, not a universal result. It closes by asking viewers to state the algorithm's invariant, asymptotic bound, and likely hardware cost separately. Companion material: algorithm article and binary-search flow.
Related articles
Algorithms Are Procedures With Costs
Learn to connect an algorithm's correctness argument to the comparisons, branches, and memory accesses it performs.
Arrays and Memory: How Indexing Works
Why array indexing is O(1), how the CPU computes element addresses, and what spatial locality means for performance.
Recursion: Functions Calling Themselves
How a function can solve a problem by delegating a smaller version of the same problem to itself, the call stack, and common pitfalls.
More in Programming & Algorithms
Advanced Algorithms: Sorting, Graphs, and Dynamic Programming
Master sorting, graph traversal, and dynamic programming through execution traces that reveal the mechanics behind the algorithms.
DetailsLearning Algorithms from Scratch
A beginner-friendly walkthrough of what an algorithm is, how arrays store data in memory, and how simple search and insertion traces execute.
DetailsData Structures and Algorithms: From Arrays to Trees
Master arrays, hash tables, trees, and recursion through execution traces that show what actually happens in memory.
DetailsNew lessons by email
Get new articles and notes on the systems behind everyday software.
One technical dispatch per week. No noise.
Not started
Sign in to save your learning progress.