Asymptotic Notation

                       Asymptotic Notation is a concept of analysis Algorithms for best case, average case and worst case. For all the three cases we need to identify the upper bound, lower bounds using syntax and Notation .

Big-O Notation

---

This notation gives the tight upper bound of the given function.

In general we represent algorithm in the form of function f(n)

f(n)= O(g(n))

This means, for larger values of n, The  upper bound of f(n) is g(n).

For example, if algorithm is given
f(n)=n²+10n+5
Then n² is g(n), g(n) gives the maximum rate of growth for f(n) at larger values of n.

Big-O Visualization

      O(g(n)) is the set of functions with smaller or same order of growth as g(n).

      For example, O(n²) includes O(1), O(n), O(nlogn).

Omega-Ω Notation

---

This notation gives the tighter lower bound of the given algorithm.
Represent as f(n)= Ω(g(n))

At larger values of n, the tighter lower bound of f(n) is g(n).
Example, if

                  f(n)=10n²+5n+2 , g(n) is Ω(n²)

Theta-θ Notation

---

    This notation decides whether the upper and lower bounds of a given algorithm are same or not. The average running time of algorithm is always between lower bound and upper bound.

If the upper bound (O) and lower bound (Ω) gives the same result then θ notation will also have the same rate of growth.

For Example, f(n)=5n+n , Then tight upper bound g(n) is O(n).

Rate of growth is g(n) is O(n)