Let's be precise. I'm being more precise here in my comment than I was on Quora.

Big-O and related notations are ways of categorizing functions. O(n^2) for example is actually a set of functions, which is why I wrote f ∈ O(n^2) rather than something like f = O(n^2) or f(n) = O(n^2). That is, f is a member of some set of functions which all satisfy a particular, precisely-defined property.

To understand that property, first, let's get rid of the idea of "performance" because asymptotic analysis has nothing to do with "performance" per se and predates even the first precise definitions of things like "algorithm" or "computability." The notation itself was invented in the late 19th century.

Instead, let's just talk about "upper bounds." If we have a function it's easy to talk about upper bounds. For example,

f(x) = sin(x)

is bounded above by 1, 1.5, 10, 100, 80457, and an infinitude of other numbers for any real number x. It's bounded below by -1.

Now, in this case, it's east for us to see that not only is

sin(x) <= 1 for all real x

but also that

max { sin(x) : x is real } = 1

So in this sense the upper bound of 1 is strict. 2 is also an upper bound in the sense that

sin(x) <= 2 for all real x

but it's not strict. There are other upper bounds which are strictly smaller than 2, e.g., 1.5. So, we can say that "the value of sin(x) for real x is no greater than 2," but we can't say that it "is" 2.

So, to answer your point before diving deeper, Big-O is about "worst case performance" in this sense. By itself it doesn't tell us what the worst case performance is. Instead, it gives us an upper bound on the worst case performance. It says "the worst case performance is no worse than FOO." The actual worst case performance might be better.

Big-Θ is the asymptotic equivalent to "this is a tight upper bound."

I'll skip further development of this for now and jump back to the issue of algorithms. The issue is this: given an algorithm with input of length N, we want to say something about how long it takes to run.

This means that the function we're analyzing isn't "QuickSort(n)". What does that even mean? The input of QuickSort is an array of integers and it returns a sorted array of integers. How can an array of anything be greater than or equal to n^2? So that's one way in which the CS vernacular equivocates -- we're not really talking about QuickSort we're talking about some other function:

T(n) = the amount of time it takes QuickSort to run given an input of length n

We're then talking about bounds on this other function T, asymptotic or otherwise.

But now we're in a pickle because what does "the amount of time it takes QuickSort to run given an input of length n" mean? There are many inputs of length n. If we're talking about just arrays of integers of length n, there are n! if all we care about is relative ordering and not the actual values in the array. If we care about the actual values in the array then there are an infinitude of inputs of length n.

There are a few ways we can handle this. Let's re-define T(n) like so:

T(x) = the amount of time it takes QuickSort to run given input x

One way is the "worst case" method. This says, ok, look at this function:

W(n) = max { T(x) : x is a valid input to QuickSort and len(x) == n }

We can now do Big-O, bounds, asymptotic analysis, etc. on W(n). This is what we mean when we say the worst case is O(n^2). It means W ∈ O(n^2).

Another way is the "average case" method. This says, ok, look at this function:

A(n) = avg { T(x) : x is a valid input to QuickSort and len(x) == n }

This is tricky if there are in principle an infinite number of valid inputs of a given length. There are various ways of handling this issue. For something like QuickSort we can see that it's really only the ordering that matters, i.e., for the purposes of QuickSort [1,10,5] is the same operation-wise as [-50, 80, 0], so there are only n! inputs we really need to check for a given n.

Yet another way is the "best case" method, which looks at

B(n) = min { T(x) : x is a valid input to QuickSort and len(x) == n }

So, given an algorithm we can derive these three functions and then answer Big-O questions about them. We're never answering Big-O questions about the algorithm per se, although we can get away with equivocating when W(n), A(n), and B(n) are always equal or it's obvious we only care about one of them.

For simple examples this is often the case, e.g., calculating the nth Fibonacci number in the standard iterative way has best, average, and worse case performance of O(n).

To make matters worse, most people say Big-O but mean Big-Θ, or at the very least aren't clear when they mean one or the other. So, when one says "worst case performance" and we have W(n), A(n), and B(n) all being the same, it can be particularly confusing.

Depending on the algorithm in question which it might be understood what we care about one more than the others. For example, if worst case inputs are particularly pathological we might talk as if we mean the performance of the algorithm per se but really be talking about A(n). However, if "bad" inputs are common we might really be talking about W(n).