Time Complexity 3 – Asymptotic Notations

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

Link to test this

• What is it a time complexity?
• Time complexity and how to count complexity of your algorithm.