> For the complete documentation index, see [llms.txt](https://til.kurianbenoy.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://til.kurianbenoy.com/programming/asymptotic-time-complexity.md).

# 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.

![](/files/-Mjp8mKJMt1DB9JicTJR)