Thinking & complexity: predict then measure

Build a 'predict-then-measure' benchmark that runs at least four algorithms of different complexity classes over a range of input sizes, then show that the measured growth (operation counts and timings) matches the Big-O you predicted from the code — and explain every place where it does not.

• Implement at least four algorithms spanning distinct classes: one O(1) (e.g. array index lookup), one O(log n) (binary search on a sorted array), one O(n) (linear scan / sum), one O(n²) (nested-loop duplicate check or all-pairs). Add an O(n log n) sort for a stretch comparison if you like.
• For each algorithm, write down your PREDICTED Big-O for time and for space before running anything — derived by counting loops and memory, not by measuring.
• Instrument an operation counter (increment on each basic comparison/step) so you measure work independently of CPU speed, plus a wall-clock timer for context.
• Run every algorithm over a doubling sequence of input sizes (e.g. n = 1k, 2k, 4k, 8k, 16k, …) and record operation count and time for each (n, algorithm) pair.
• Produce a results table and, for each algorithm, the RATIO of cost at size 2n to cost at size n — this ratio is the fingerprint of the class (≈1 for O(1), grows by a small additive step for O(log n), ≈2 for O(n), ≈4 for O(n²)).
• Demonstrate the time-space tradeoff concretely: include both the O(n²)-time/O(1)-space and the O(n)-time/O(n)-space duplicate check and report both their timings and their peak extra memory.
• Use the rule of thumb (~10⁸ ops/sec) to predict, for one algorithm, the largest n that finishes in ~1 second, then run near that n and check your prediction against the measured time.

• A predicted-vs-measured table: for each algorithm, the Big-O you predicted next to the doubling ratio you measured, with the two agreeing (O(n)≈2×, O(n²)≈4×, O(log n) a small additive step, O(1) flat).
• The O(n²) algorithm's cost is shown overtaking the O(n) algorithm as n grows, with the crossover (and any small-n region where the 'slower' class wins due to constants) explicitly noted.
• A short write-up reconciling every mismatch — e.g. noise at tiny n, constant factors, or a doubling ratio that only converges to the theoretical value as n grows large.
• The duplicate-check comparison reports both time and extra memory for each approach and states which constraint (latency vs memory) would make you pick each one.
• Your ~1-second prediction from the 10⁸ ops/sec rule lands within an order of magnitude of the measured result, with the gap explained (constant factors, language overhead).