djmullen
Posts: 327 Joined: Jan. 2006

I've got a question about the No Free Lunch theorems. I hope somebody can clarify things for me.
I don't claim to understand the math behind NFL, but from reading the commentary, I get the impression that the theory says that there is no single search strategy that will work perfectly for ALL possible search spaces and data arrangements. For example:
If you have an array set up like this:
1: apple 2: cow 3: echo 4: FTK 5: Geronimo 6: salivate
A simple binary search type algorithm will let you find the word "echo" in the array in three steps or less because the entries are in alphabetical order.
But if the array is arranged like this:
1: cow 2: salivate 3: FTK 4: apple 5: Geronimo 6: echo
The binary search algorithm won't work.
Furthermore, the NFL theorem seems to say that, averaged over all possible arrangements of the data in the array, no single algorithm will work better than a random search, where you choose a number at random, look at the word in that position, see if it's the word you're looking for and repeat the search if it isn't.
Finally, the big thing about the NFL theorem is that it was mathematically proven a few years ago. Is this more or less right?
