Sedgewick & Wayne · §4.2 Sorting and Searching

Sequential Search: Hits, Misses, and Quadratic Time

Check each entry in turn until you find the key or run out of array. A hit stops early, after about N/2 compares on average. A miss always checks all N entries. Make the number of searches grow with N too, and the total work is quadratic.
1 · Trace one search
The 15-name whitelist from the lecture slides. Pick a key and step through the loop one compare at a time.
Test for equality with
Compare log
2 · Average cost of a random search
Run 1,000 random searches on a whitelist of N random strings and count the compares each one needs. For a random hit, each entry is equally likely to be the key. For a random miss, the key is not on the list.
30
Searches
1 compareN compares
measured average–
predicted–
searches run0
3 · Whitelist filter scenario: doubling test
As in the slides: a whitelist of N random 10-letter strings (a–z) and 10N searches. Each row doubles N. We count compares rather than seconds, so the result doesn't depend on your computer.
Search keys
Nsearches (10N)total comparesper searchratio
Press “Run doubling test”.

Everything here runs live in your browser: the whitelist in panels 2 and 3 is generated fresh each run, the same way Sedgewick's Generator does it, and every compare is actually executed and counted. In panel 1, == never matches because in Java two strings read at runtime are different objects, even when they hold the same characters.