2.2 Asymptotic Analysis

Asymptotic Analysis

Asymptotic analysis is a mathematical approach to evaluate the performance of algorithms in terms of their resource usage (e.g. time or space) as the size of the input data ($n$) grows infinitely large. Instead of focusing on exact execution times, it provides a generalized way to express the efficiency of algorithms by describing their growth rates and behavior as input sizes increase using the following notations:

• $O$-notation (big-oh notation) characterizes an upper bound on the asymptotic behavior of a function $f$, such that it may not run faster than a certain rate. In other words, $O$-notation is the set of all functions that run slower than (or equivalently slow to) $f$. Formally, for a given function $g$, $O$-notation states that there exist positive constants $c,n_0>0$ such that
  $O(g(n))=\{f(n):0\le f(n)\le cg(n)\text{ for all }n\ge n_0\}.$
• $\Omega$-notation characterizes a lower bound on the asymptotic behavior of a function $f$, such that it grows at least as fast as a certain rate. In other words, $\Omega$-notation is the set of all functions that run faster than (or equivalently fast to) $f$. Formally, for a given function $g$, $\Omega$-notation states that there exist positive constants $c,n_0>0$ such that
  $\Omega (g(n))=\{f(n):0\le cg(n)\le f(n)\text{ for all }n\ge n_0\}.$
• $\Theta$-notation characterizes a tight bound on the asymptotic behavior of a function $f$, such that it runs precisely at a certain rate. It is the set of all functions that run just as fast as $f$. Formally, for a given function $g$, $\Theta$-notation states that there exist positive constants $c_1,c_2,n_0>0$ such that
  $\Theta (g(n))=\{f(n):0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\text{ for all }n\ge n_0\}.$

Moreover, for any two functions $f(n)$ and $g(n)$, if $f(n)=O(g(n))$ and $f(n)=\Omega (g(n))$, then $f(n)=\Theta (g(n))$, meaning that $f(n)$ is tightly bound by $g(n)$ from both above and below.

Proper Abuse $=$) instead of the set membership sign ($\in$) within formulae. There are two different ways of interpreting this notation:

Although we formally define asymptotic notation in terms of sets, we use the equal sign (

• When the asymptotic notation stands alone (e.g. $O(n^2)=4n^2+100n+500$), the equals sign means set membership ($⟺4n^2+100n+500\in O(n^2)$).
• When the asymptotic notation appears in a formula (e.g. $2n^2+3n+1=2n^2+\Theta (n)$), it stands for some function that has been abstracted ($⟺2n^2+3n+1=2n^2+f(n)$ where $f(n)=3n+1\in \Theta (n)$).

Intuition