Big O is not necessarily about execution time. Also, why is it ridiculous to describe execution time as "time complexity"? From http://en.wikipedia.org/wiki/Analysis_of_algorithms "Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity)."
> Also, why is it ridiculous to describe execution time as "time complexity"?
It's unnecessarily different than the normal definition of "complexity." When you say "complex" in normal conversation, you mean "complicated" or "hard to understand." You would never say "the time complexity of getting to the airport is 30 minutes."
It also begs the question. Wrapping your head around the idea of asymptotic complexity is the hard part of understanding big O. Defining big O in terms of complexity doesn't help if you don't understand the concept of asymptotic complexity yet.
I think the best way to explain this, by far, is with a graph.
If the definition uses "complexity" in this way then it's not using it in the "plain English" sense, but in a specialized sense. Quantity isn't complexity.
You can talk about memory usage just as easily with big O as execution time (or space complexity vs time complexity).
A plain English explanation of Big O notation shouldn't take more than a few sentences. It's not that complicated, especially if you don't get into nitty gritty.