Here's an answer of mine on Quora you might find useful:
https://www.quora.com/Algorithms/How-can-I-determine-whether...There are two things going on.
First, when we talk about Big-O we're not talking about the "worst case scenario." Big-O gives us an upper bound on the worst case scenario, but the actual worst case scenario might be better. Big-O means "no worse than" not "as bad as."
When most people say Big-O they really mean Big-Θ, which does encapsulate the idea of "asymptotically equivalent, up to a constant." See my answer on Quora for more technical details.
Second, Big-O and other forms of notation used in the asymptotic analysis of functions were invented before physical computers existed. They're statements about pure functions.
When applied to the analysis of algorithms the function we're "really" analyzing isn't the algorithm. Rather, if we have an algorithm A that takes as its input a positive integer n, we're really analyzing the function "the length of time it takes algorithm A to run given input n."
The up-to-a-constant nature of Big-O notation is nice because that constant can encapsulate things like processor speed, memory access times, and so forth. This enables us to make intelligent statements about algorithms per se without reference to the underlying machine on which the algorithm might be implemented.
Even with ideal functions, this naïve asymptotic analysis has some problems. For a toy example, imagine a spiky function like this:
f(n) = 800*n^2 if n is divisible by 1000000000
f(n) = 400*n otherwise
This function is not O(n) but it is O(n^2). The "worst case" behaves like O(n^2), but for "most inputs" it behaves like O(n). We can't say "f(n) is asymptotically no worse than n, up to a constant" because for infinitely many inputs it is.
Lots of algorithms behave like this in practice because we optimize for common cases perhaps at the expense of less common cases. "Common" is dictated by how our algorithm is used.
Taking quicksort as an example, let's call the algorithm Q. We want to measure its running time given an input of length n. For input x, let's say it's running time is T(x).
Well, there are many x such that len(x) == n, so what does it even mean to say "its running time given an input of length n?" Are we given a particular input of length n? A uniformly-selected-but-random input of length n? To the extent that we can, we want to be making statements about the algorithm per se, not statements about the algorithm given a particular input.
On way to answer this to ask "Given an input of length n, what's the most time my algorithm could take?" In that case we're analyzing the following function:
W(n) = max { T(x) | x is valid input and len(x) == n }
On the other hand, maybe we care more about the average case. Perhaps we randomly pick 1,000 inputs of length n and average the running time. Now we're talking about something that looks more like a probability distribution than a discrete thing like "running time" because we've sampled the input space.
And in fact, we could calculate "expected running time given input n" in this way and graph that. We could then make Big-O like statements about that new function, which is the kind of thing folks mean when they talk about "average case."
Hope that helps!