Brave computer science student gets test question right.

I don't know if the student was "brave" so much as "did not know how to demonstrate that you cannot find the median of an unsorted list without examining every item in the list".

A quick and fairly informal sketch of the proof: here's a three element list: 1, 2, N. If you tell me which of those three is the median without known N, then I can always surprise you with an N such that your guess is wrong (you guess 1 or 2, surprise, N was 0. You guess N, surprise, N was -1).

Now append negative MAX_INT and positive MAX_INT to the list.

The size of the list is now 5, and the median must be either 1, 2, or N. Care to take a guess prior to me revealing N? Whoops, looks like you lose again.

We can keep playing this game for any size of list you want to play with greater than zero: for any size of list I can create at least one list such that not knowing one number makes the median unknowable. (I could show you for an even number of elements, too, but won't for brevity.)

Thus, since you can't calculate the median of a list in less than O(n), you can't use "calculate the median and..." in any procedure you claim has a big-O complexity less than O(n).

Thought this would be much more HN-y if there was a prospect of the problem actually mattering in the real world, rather than being a pair of poor jokes on a CS exam.

Not as novel as I was expecting, but still worth a small chuckle. :-p

"Undoubtably" is also spelled incorrectly.