Lucy and the Linear Search
My wife and I are reading C.S. Lewis’ The Voyage of the Dawn Treader together before we go see it in the theater. We stumbled upon this nice little discussion on computational complexity in chapter 10:
One thing that worried [Lucy] a good deal was the size of the Book. The Chief Voice had not been able to give her any idea whereabouts in the Book the spell for making things visible came. He even seemed rather surprised at her asking. He expected her to begin at the beginning and go on till she came to it; it obviously wouldn’t have occurred to him that there was any other way of finding a place in a book. “But it might take me days and weeks!” said Lucy, looking at the huge volume, “and I feel already as if I’d been in this place for hours.”
To the Chief Voice’s credit, he could have favored the much worse bogosearch, cousin to the bogosort.