As I wrote in my introductory post, I have needed to know most of these things in my day-to-day job. Of course, it depends on what sort of work you're doing.
I don't need to know these things in my day-to-day job either. However, if I did need to know them, they'd be a Google search away, and I could find them out in less than a minute (less than the time it takes me to get urllib2 to send cookies, for example).
On the other hand, I imagine that someone who hasn't been formally trained in complexity would have a harder time, because they wouldn't be aware of basic concepts such as complexity, the O notation, etc. Therefore, asking whether someone knows what O(n) means strikes me as a better performance test than trivia like the difference between O(2^n) and O(3^n).
The difference between O(2^n) and O(3^n) isn't trivia; if you can answer the question, then you have an understanding of what big-O means. Asking someone to recite the definition they learned of O(n) is easy; asking someone to think critically about the definition of big-O and how 2^n and 3^n relate shows a deeper understanding. I haven't memorized any trivia relating to these functions, but I convinced myself within a few seconds of the answer from the definition of big-O.
Yeah, bad example there. The asymptotic running time of the heap operations, or quicksort runtimes, for example, though, were more like trivia, even though you can basically get them if you know the algorithms and reason about them a bit.
I know the running time of quicksort offhand, but I'd still consult wikipedia on the off chance I'm wrong.
An interesting side project of this would be describing how the difference between O(2^n) and O(3^n) or knowing what the heap operations are have been needed in your job.
And, since I'm asking already, I'd also like to know why you needed to know the information "on-the-fly" and couldn't have gotten there almost as easily with a quick refresher.
For example, I don't remember all the heap operations by heart but, if I needed to select a data structure for a critical task, I would go fetch Cormen and Skiena (the books, not the people) and get a quick refresher.
