Exercise 1: Checking for an Order ID at the Front of the List — Possible Solution ==================================================================== THE TEST ------------------------------ Using this chapter's own 20,000-order list, checking for 'ORD-0' (the FIRST item inserted) instead of 'ORD-19999' (the last item, this chapter's own worst-case test): linear check, ID first in list: 0.084 microseconds linear check, ID last in list: 146.319 microseconds set check, ID first in list: 0.077 microseconds linear-first is faster than linear-last by: 1738x VERIFYING THE DRAMATIC TIMING CHANGE ------------------------------ Checking for the first-inserted ID took 0.084 microseconds - almost identical to the set check's own 0.077 microseconds, and roughly 1,738 TIMES faster than checking for the last-inserted ID (146.319 microseconds) against the exact same 20,000-item list. WHY THIS HAPPENS, USING THIS CHAPTER'S OWN O(n)/O(1) FRAMING ------------------------------ Python's `in` operator on a list performs a linear scan starting from index 0 and stopping the instant it finds a match. Searching for 'ORD-0' means the very FIRST comparison succeeds - the scan barely begins before it's done, regardless of how many more items sit behind it in the list. Searching for 'ORD-19999' (this chapter's own test) means every single one of the 19,999 items before it has to be checked and rejected first - the true O(n) cost this chapter's own finding measured. The set check stayed flat in both cases (0.077 vs. this chapter's own 0.080 microseconds) because a hash lookup doesn't scan anything at all - it computes a hash and checks one bucket, regardless of where the matching item was originally inserted. WHY THIS IS AN IMPORTANT CAVEAT, NOT A CONTRADICTION ------------------------------ This doesn't undermine this chapter's own finding - it sharpens it. The linear check's real-world cost depends entirely on WHICH id is being searched for, which in a real system is unpredictable (a customer could place an order with any ID, and a duplicate-check would need to handle the worst case reliably, not just the lucky cases). This chapter's own worst-case test (checking the last-inserted ID) was the honest, representative choice - a benchmark using only best-case lookups would have hidden the exact bottleneck this chapter was trying to demonstrate. WHY THIS WORKS AS AN ANSWER ------------------------------ The test is run using this chapter's own exact data and timing methodology, changing only which ID is searched for, and the dramatic timing difference is explained by tracing exactly how Python's linear scan behaves differently depending on a match's position - not just reported as a number.