Other Common Asymptotic Notations and Why Big (O) Trumps Them

Explore other common asymptotic notations such as Big Omega, Big Theta, little o, and little omega, and understand their mathematical definitions and applications. Learn why Big O notation is typically favored in algorithm analysis, particularly for characterizing worst-case time and space complexity, enabling you to better analyze and compare algorithm efficiency.

We'll cover the following...

Big ‘Omega’ - Ω(.)
Why Big ‘O’ is preferred over other notations

Big ‘Omega’ - $\Omega(.)$

Mathematically, a function $f(n)$ is in $\Omega(g(n))$ if there exists a real constant $c > 0$ and there exists $n_o > 0$ such that $f(n) \geq cg(n)$ for $n \geq n_o$ . In other words, for sufficiently large values of $n$ , $f(n)$ will grow at least as fast as $g(n)$ .

It is a common misconception that Big O characterizes the worst-case running time while Big Omega characterizes the best-case running time of an algorithm. There is no one-to-one relationship between any of the cases and the asymptotic notations.

The following graph shows an example of functions $f(n)$ and $g(n)$ that have a Big Omega relationship.

1.Introduction

2.Algorithmic Paradigms

3.Asymptotic Analysis

4.Sorting and Searching

5.Dynamic Programming

6.Greedy Algorithms

7.Divide and Conquer

8.Graph Algorithms

9.Appendix: Auxiliary Source Code

10.Conclusion

Other Common Asymptotic Notations and Why Big (O) Trumps Them

Big ‘Omega’ - $\Omega(.)$

Big ‘Theta’ - $\Theta(.)$

Other Common Asymptotic Notations and Why Big (O) Trumps Them

Big ‘Omega’ - Ω(.)\Omega(.)Ω(.)

Big ‘Theta’ - Θ(.)\Theta(.)

Big ‘Omega’ - $\Omega(.)$

Big ‘Theta’ - $\Theta(.)$