Computing / Preview lesson sketch 03
Algorithms and cost
Compare procedures by how their required work grows, not by one stopwatch reading.
It remains available from the sealed 0.1 preview while the deeper Foundations format is reviewed and expanded. No study-time claim is made.
orient
Why this idea had to exist
Two programs can return the same answer while behaving very differently as inputs grow. Algorithm analysis isolates the structure of that growth before hardware and implementation details enter the picture.
intuition
Build a picture you can reason with
Imagine increasing the input dial. A constant-time operation barely moves its work meter; a linear scan tracks the dial; a quadratic pairwise comparison rises much faster. Growth class describes the shape of that response.
formalize
Give the intuition a precise edge
T(n) is O(g(n)) when constants c and n₀ exist such that T(n)≤c·g(n) for n≥n₀. The notation provides an asymptotic upper bound. Space complexity tracks additional storage with the same discipline.
work through
Follow the decisions, not just the symbols
Binary search halves a sorted search interval each step. After k steps, n/2ᵏ≤1, so k grows like log₂n. The speed comes from the sorted invariant and the decision that discards half the candidates.
experiment
Change one thing and watch the model answer
Trace linear and binary search over increasingly large collections. Count comparisons rather than milliseconds, then plot how those counts change when input size doubles.
retrieve
Close the page and reconstruct it
Answer before opening the explanation. Retrieval is evidence only when the answer is produced without a hint.
Why can binary search not be applied directly to an unsorted list?
Its correctness depends on order: a comparison can discard half the list only when values on each side obey the sorted invariant.
transfer
Move the idea into a new setting
Compare two ways to detect duplicate identifiers and explain the time-space tradeoff rather than naming only the fastest option.
reflect
Leave with a diagnostic habit
State the input size, dominant operation, invariant, and worst relevant case. Complexity claims without those choices are incomplete.
Source record
Follow the sketch back.
- Reference
- Open Data Structures
- Publisher
- Pat Morin
- Locator
- Whole-source locator retained from v1; precise locator required before conversion.
- Review
- Pending