Skip to main content

Asymptotic Notation

One of my reading projects is to work on the Introduction to Algorithm.

After a few chapters I realized that I might have already forgot all little pieces of mathematics learned in college.

This note shall keep me aware of the asymptotic notations frequently used in the algorithms:

\(f(n)=\Theta(g(n)) \Leftrightarrow c_{1}g(n) \le f(n) \le c_{2}g(n)\)

\(f(n)=O(g(n)) \Leftrightarrow 0 \le f(n) \le cg(n)\)

\(f(n)=\Omega(g(n)) \Leftrightarrow 0 \le cg(n) \le f(n)\)

\(f(n)=o(g(n)) \Leftrightarrow \lim \limits_{n \to \infty} \frac{f(n)}{g(n)}=0\)

\(f(n)=\omega(g(n)) \Leftrightarrow \lim \limits_{n \to \infty}\frac{f(n)}{g(n)}=\infty\)

To make the notations easier to remember/understand, the book gives the following loose analogies:

\(f(n)=\Theta(g(n)) \approx f(n) = g(n)\)

\(f(n)=O(g(n)) \approx f(n) \le g(n)\)

\(f(n)=\Omega(g(n)) \approx f(n) \ge g(n)\)

\(f(n)=o(g(n)) \approx f(n) < g(n)\)

\(f(n)=\omega(g(n)) \approx f(n) > g(n)\)