Interview Questions: What is the Big O notation of X?

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²) 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²) process would take over a day to process the same set of information.

An algorithm that runs a single for loop on a set of data would be O(n), because it only processes one iteration for each item (hence, n¹); an algorithm that runs a for loop on a set of data, then has another for loop processing the entire set within each iteration of the first for loop, processes the entire set once for EACH item in the set (hence, n²).

A great explanation of Big O notation is available here: http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html

I've seen this question come up in about half of the jobs I've interviewed for, so it's good to be able to understand it and explain it.