Big-O notation for other cases

Question

I was just reading answers to a question Plain English explanation of Big O From that i came to know that Big-O notation is just an "upper bound" of the complexity of an algorithm?

But can we apply it to other cases(i.e best and average case) of an algorithm?

Answer 1

Yes, you can apply it to other cases.

Big-Oh basically says "no matter how you stack the deck against this algorithm, at worst its performance will scale this way compared to the input."

Omega is similar, but means "no matter how good you make its inputs, at best its performance cannot scale any better than this compared to the input."

For example, quicksort is a popular sorting algorithm. It is actually O(n²) because at worst it has quadratic performance (bad pivot choice). At best it is Ω(n log₂ n) which is actually the best that any general-purpose sorting algorithm can possibly achieve.

Answer 2

Big-Oh describes the growth rate of a set of functions by comparing it to the growth rate of another function. What those functions mean is totally irrelevant to Big-Oh. It could be a function describing the worst-case time complexity of an algorithm. It could be a function describing the best-case time complexity of an algorithm. It could be a function describing the average case time complexity of an algorithm. It could be a function describing the amortized worst-case time complexity of an algorithm. It could be a function describing the worst-case step complexity of an algorithm. It could be a function describing the worst-case space complexity of an algorithm. It could be a function describing the amount of humans in the world. It could be a function describing the amount of money a movie makes in relation to its production cost.

Answer 3

Sure the three main notations are:

"Big-Oh" meaning your function is always <= c*f(x) for some constant c and values greater than some x.

"Big-Omega" meaning your function is always >= c*f(x) for some constant c and values greater than some x

"Big-Theta" which is used to describe a tight upper and lower bound, meaning it is both Big-Oh and Big-Omega. To show Big-Theta you should show both Big-Oh and Big-Omega are the same.

And then on top of all this sometimes you will hear about the "worst case of the best case" or "best case of the worst case" etc.

And to the person above who talks about quick sort, what about smooth sort?