## Time complexity 3 – asymptotic notations

Big-oh(*O)*, omega(Ω), theta(Θ). It sounds like some magical words, but it is just a 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 will 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 start with a big-oh

**Big-oh is a upper bound** of our algorithm function.

What does it mean?

Simply said, we have a function that describe complexity of algorithm and that function looks like this:

f(n) = 3n^2 + 2n + 1

then we have a 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 start with example again and we will keep the same function:

f(n) = 3n^2 + 2n + 1

then we have a 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 a upper bound

Big omega Ω is a lower bound

Big theta Θ is a upper and lower bound

I hope that I clarify these three “magic” words for you and that from now on you will be able to explain what they means.

**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

and lower bound is called omega

and it can be for example

n^3

Time complexity and how to count complexity of your algorithm.