Aymptotic Notation

So, let's learn about some mathematical tools which you can use to study, analyse and compare algorithms. Unfortunately, this is highly mathematical..

Big - Oh Notation






Big Omega Notation

Just as O-Notation provides an asymptotic upper bound on a function, the omega notation provides an asymptotic lower bound.





Asymptotic Notations in Equations in Inequalities (Macro convention)
The asymptotic notation can also be used in mathematical formulas. We have already defined the Big-Oh notation as a set. What happens when a set appears in a mathematical formula? What happens when we use O-Notation in a formula e.g.

Till now, we only defined O-notation, as something equals O(some other thing).
But it is useful to have big-Oh in a general mathematical expression.

A set in a formula represents an anonymous function in that set.






Theta Notation





So, the theta notation provides not just the asymptotic bounds but tight asymptotic bounds. In practice, we always want tight upper and lower bounds.

Strict's Notation - Little Oh and Little Omega
Like Big Oh and Bog-Omega notations, we have little Oh and little Omega notations.The bounds they provide are not asymptotically tight.