This Is How I Think Now. You're All Stacks and Queues.
January 08, 2004, 04:07 pmOver Christmas break, my dad told me that he saw someone that asked him to say "Hi" to me, but he wanted me to guess:
- is this person a man? no.
- is this woman older than 35? yes.
- was this woman a teacher of mine? yes.
- was this woman a high school teacher of mine? yes.
Ultimately, I couldn't guess who it was (because I couldn't remember
any female high school teachers at the time), but that's not the point
of this story. The point is that every question I asked essentially
divided the potential candidates in half. Any CS geek will recognize
this as the binary search algorithm (aka, Divide-and-Conquer), which
has a performance of O(log2 n) (where
n is the total number of candidates).
So if I know a total of 1,024 people (which I don't think I do) it would take me a maximum of 10 questions to determine who it was (provided that I could actually remember everyone).
In case you hadn't realized, I'm a huge dork.