What’s the difference between "Big O", "Big Theta" and "Big Omega"?

Question

What use are each of these "Big O", "Big Theta" and "Big Omega" and when to use each to describe the complexity of an algorithm?

Answer 1

This is a controversy already discussed before another question I answered and some people said I was wrong. And I was wrong, for academics. Yes, academics define this in a different way than how people use it in day-to-day programming (at least for some, some people say it’s good for nothing, it must be the same people who then need to resort to complex solutions because everything is slow), so it’s complicated, these concepts suffer prejudice from everywhere :) You didn’t say what definition you want, because you probably don’t know that there is such a difference. I go from pragmatic engineers.

Read What is an asymptote?.

Big O is the worst case of an algorithm, you make an analysis of how many steps at most something will be used to complete the task, so we usually say that you are calculating the maximum time that the algorithm will perform, even if this does not serve to measure real time, only a proportion.

Some people think it’s possible to calculate the exact time. And it even does, but it’s impractical in most situations and it can only be the idea of academics to do this, you have to know all the details of implementation and deployment to get to this number that turns out to be irrelevant, because it is more easily observable. On the other hand if you don’t know what his basic behavior would be like, because without it you won’t know how to fix something that is taking too long, anything can happen.

The Big Omega is the best case that it will perform, but usually it is not relevant information outside the academy, there are exceptions (probably when using real time).

The Big Theta wants to know the average complexity of execution (it is not that it is the arithmetic mean itself, it is between the previous measures, but it is something that generates a less predictable value), so he expects it to be between the two previous concepts. In many cases the (real) average is what we want to know for real mainly if the average or next of this is what will happen the most.

I’ve explained before, if you’ve read the links, that there are algorithms that the strict Big O of many algorithms are pretty bad, for example searching in a table hash has Big O real O(N), usually even a little more than that, but a little, maybe an O(N+k) or O(N+M) where M is a low number that needs to be calculated by another formula. In many cases what you use as Big O is actually Big θ, or something close to that. In others only ignore the exceptions that can happen (the example I quoted now has constant complexity in most cases, in some it has a slightly higher cost, which can rather be linear, but which in practice never happens, so one ignores this for most analyses, but can not at all, then the academics are wrong and the "too pragmatic").

There are some algorithms that even have the same complexity, but only when we analyze them superficially, which for practical purposes is enough, so the approximate Big θ occurs a lot, and nobody gives the smallest pellet to him.

So when you look at the table of this website, Don’t think you’re using real Big O, or any other Big, there’s a pragmatic approach to what’s important to most of the analyses that engineers do. If you are aware that it is a simplification you are using well.