Big-oh(O), omega(Ω), theta(Θ). It sounds like some magical words, but it is just math. So don’t be scared and I will show you what it means and how to deal with it.
First of all, I would like to say that before you read this post, you should read this one and this one about time complexity of an algorithm and why it is so important for a developer to know this.
Let's start with a big-oh.
Big-oh is an upper bound of our algorithm function.
What does it mean?
Simply said, we have a function that describes complexity of algorithm and that function looks like this:
f(n) = 3n^2 + 2n + 1
Then, we have another function that is upper bound for our function f(n):
g(n) = k*n^2
when n=1
3*1 + 2 + 1 = 6
6*1 = 6
f(n) = g(n)
when n=2
3*2 + 4 + 1 = 11
6*2 = 12
f(n) < g(n)
etc....
f(n) is always less than or equal to g(n), for k=6 and n >=1.
Informal and formal definition
Formal definition contains 
and it is the lowest number n for which it works. In our case, it is n = 1.
Graph
Big omega is a lower bound of a function
Let's start with an example again and we will keep the same function:
f(n) = 3n^2 + 2n + 1
Then we have another function that is lower bound for our function f(n):
g(n) = n^2
Informal and formal definition
Simply said, it means than our function f(n) will be always bigger than our lower bound g(n).
Graph
Last one is Big theta and it is lower and upper bound so you can use the same functions that we discussed before.
Graph
Informal and formal definition:
Summary
- Big-oh O is an upper bound
- Big omega Ω is a lower bound
- Big theta Θ is a upper and lower bound
I hope that I clarified these three “magic” words for you and that from now on, you will be able to explain what they mean.
Test
f(n) = 3n^3 + 5n^2 + 6n + 7
What is a upper bound of this function?, and how do we call it?
What is a lower bound of this function?, and how do we call it?
Result
Upper bound is called big-oh and for this function, it could be for example:
n^4 for n > 5
Lower bound is called omega and it can be for example:
n^3
