A search through three shuttle stops feels immediate. A search through a million records may not. Algorithm analysis asks how the work changes when the input grows, and which assumptions make that prediction valid.
Reading route¶
Counting work: define input size and a cost model, then count operations.
Growth rates: compare scaling and interpret dominant terms.
Cases and bounds: separate input situations from upper, lower and tight bounds.
Analysing code and space: reason through loops, halving, branches and additional storage.
Correctness and proof habits: connect contracts, invariants, progress and counterexamples.
The search examples extend Topic 1. They are small enough to trace manually, but the resulting functions describe entire families of input sizes.
Before you start¶
You should be able to read basic Python loops and functions. Familiarity with powers and simple sums helps; logarithms are explained through repeated halving. No notebook or package is needed to follow the examples.
By the end, you should be able to justify a cost expression, distinguish best/worst/average cases from O/Ω/Θ notation, and state time and space claims with their assumptions.
A common analysis route¶
Across the five readings, start with the operation contract and size parameters, choose a resource and cost model, identify the input family or probability/sequence guarantee, derive the work or maximum live storage, then state a justified bound. Correctness and termination need their own arguments; the final reading works the linear-search example through that reasoning.
Use the worked counts to justify a bound before reading its simplified growth class. Later topics apply the same cost models to sorting, recursion, hashing, trees and graphs.
Use the concept index for a particular term. Continue with Recursion and divide-and-conquer. For a later application, see hash-table performance.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.