geekitarian

What the interviewer is really asking: Can you figure out the computational complexity of a situation, algorithm, or process? How to answer: It might seem like a great idea to just memorize the Big O notation of every algorithm or process you've ever heard of, but this is going to be a lot of memorization and isn't going to be as impressive as reasoning your way through a problem. Big O notation is simply a way to quickly describe how efficient some computing code is.  O(n) means that the process runs in time proportional to the amount of information processed; O(n 2 ) means that the process runs in time proportional to the amount of information processed, squared.  So, for instance, if a O(n) process is processing 10,000 pieces of data, this process might take 10,000 milliseconds (or 10 seconds) assuming that each datum requires 1 millisecond of processing; a comparable O(n 2 ) process would take over a day to process the same set of information. An algorithm th...