Onotation (pronounced bigoh notation) is a way of describing the performance of an algorithm and provides an upper bound or worst case on a function. Using Onotation you can describe the running time of an algorithm by inspecting its structure.
Upper, Lower and Tight Bound

Lower bound (\(\Omega\)) functions are those that stay below \(T(n)\) given a constant \(c\), that is, \(T(n)\leq c n\) for all \(n > 0\). In other words, lower bounding is about finding a function that given a \(c\) value always stays below \(T(n)\). e.g. given a quadratic function \(T(n)=n^2\) a lower bound function would be \(f(n)=nlog(n)\).

Upper bound (\(O\)) functions are those that stay above \(T(n)\) given a constant \(c\), that is, \(T(n)\geq cn\) for all \(n > 0\). In other words, upper bounding is about finding a function that given a \(c\) value always stays above \(T(n)\). e.g. given a linear function \(T(n) = n\) an upper bound function would be \(f(n)=n^2\).

Tight bound or exact bound (\(\Theta\)) is a combination of lower bound and upper bound. In other words, itâ€™s a function that bound \(T(n)\) from the top and from the bottom. Tight bound functions are those that stay us much close as possible to \(T(n)\) given a constant \(c\), that is, \(T(n)\approx cn\) for all \(n > 0\). e.g. given a linear function \(T(n) = n\) a tight bound function would be \(f(n) = n\), since we were able to choose a value \(c\) that satisfy the lower bound, \(f(n) = \frac12n\) and a value \(c\) that satisfy the upper bound, \(f(n) = 100n\). As a result, we could find a value \(c\) that can serve as an exact bound (\(\Theta(n)\)) for this function.
IMPORTANT: When we talk about time complexity we usually use \(O\) as \(\Theta\)
Running Time Cases
Algorithms can be classified by three running time cases:
 Worst case: This is the worst runtime behavior. The execution time upper bound uses the notation \(O(f(n))\).
 Average case: This is the expected behavior given random input data.
 Best case: This is how an algorithm performs in an ideal situation. This is also called as the lower bound and the notation used is this case is \(\Omega(f(n))\)
Performance Categories
ONotation  Name  Example 

\(O(1)\)  Constant  Get in a hash map 
\(O(log(n))\)  Logarithmic  Binary Search 
\(O(n)\)  Linear  Linear Search 
\(O(n log(n))\)  Linearithmic  Merge Sort 
\(O(n^2)\)  Quadratic  Bubble Sort 
\(O(2^n)\)  Exponential  Recursive Fibonacci 
Image by FreePhotos from Pixabay