Today IL

Search…

Python

Programming

async/await

R Programming language

C programming language

Git/Github

Databases

Asymptotic Time Complexity

During my datastructures classes in IIIT Kottayam, asymptotic time complexity was explained very well. I thought of writing the example he shared in the class:

`Consider if you are travelling from Kochi to New Delhi. You can reach the location:`

`by flight in 3 hours`

`by train in 2 days`

`by walking in 90 days`

So **big O notation**, can be such that the time required to walk is 90 days. It's considered as the upper bound such that f(n) <= cg(n).

In lowest possible time, let's say we can reach using flight. So it's the lower bound. Such that the f(n)>= c.g(n) always. It's considered **big theta notation**.

Then there is average case complexity which is means between both big O and big theta notation. It gives a tighter bound on run time such that. This is called **big theta notation** and can represented as follows

c1.g(n) <= f(n) <= c2.g(n)

We usually in industry consider even though it's considered as upper bound. It's usually considered closer to definition of big theta time.

Copy link