Asymptotic Analysis

Asymptotic analysis is a method of describing the limiting behavior of a function as the argument approaches a particular value or infinity. In computer science, asymptotic analysis is used to describe the performance or complexity of an algorithm.

This is otherwise known as complexity analysis.

Notations

There are three common notations used in asymptotic analysis:

1. Big O Notation ($O$)
2. Omega Notation ($\Omega$)
3. Theta Notation ($\Theta$)

Big O Notation

Big O notation is used to describe the upper bound of an algorithm’s time complexity. It provides an upper limit on the growth rate of the algorithm.

Mathematically, $O(g(n))$ is the set of functions that grow at most as fast as $g(n)$.

Tip

Big O notation is the most commonly used notation in complexity analysis, and can be though of as the worst-case scenario.

Omega Notation

Omega notation is used to describe the lower bound of an algorithm’s time complexity. It provides a lower limit on the growth rate of the algorithm.

Mathematically, $\Omega (g(n))$ is the set of functions that grow at least as fast as $g(n)$.

Tip

Omega notation is the best-case scenario.

Theta Notation

Theta notation is used to describe the tight bound of an algorithm’s time complexity. It provides both upper and lower limits on the growth rate of the algorithm.

Mathematically, $\Theta (g(n))$ is the set of functions that grow at the same rate as $g(n)$.

Tip

A $\Theta$ bound existing implies $\Omega =\Theta =O$ and its converse, as $\Omega$ and $O$ are the lower and upper bounds of $\Theta$.

Simplifying Notations

When analyzing the time complexity of an algorithm, we often simplify the notation to the dominant term. This is because the dominant term is the term that grows the fastest as the input size increases.

Therefore, when analyzing the time complexity of an algorithm, we often drop the lower-order terms and the coefficients of the dominant term.

Example

Consider the following function:

$\Theta (f(n))=3n^2+5n+2$

The dominant term in this function is $3n^2$. Therefore, the time complexity of this function is $\Theta (n^2)$.

Example

Consider the following function:

$\Theta (f(n))=5{\log }_2(n)$

The dominant term in this function is ${\log }_2(n)$. Therefore, the time complexity of this function is $\Theta (\log n)$. The base of the logarithm is not relevant in big O notation, as it is a constant factor, as proven by the change of base formula.

Common Notations

The following table summarizes the common notations used in asymptotic analysis:

Calculating Time Complexity

Oftentimes, it is useful to calculate the work done at each “level” of an algorithm. This can be done by summing the work done at each level and then simplifying the notation to the dominant term.

Example

Consider the following algorithm:

int sum = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        sum++;
    }
}

The work done at each level is as follows:

• Level 1: $n$ operations
• Level 2: $n\times n=n^2$ operations

Therefore, the total work done by the algorithm is $\Theta (n^2)$.

Tip

In mathematics, there are a few summation formulas that are useful for calculating the work done at each level of an algorithm:

If the work follows a sequence of $1,2,3,\dots ,n$, the sum is $\frac{n(n+1)}{2}$, which simplifies to $\Theta (n^2)$.

If the work follows a sequence of $1,2,4,8,\dots ,2^k$, the sum is $2^{k+1}-1$, which simplifies to $\Theta (2^k)$.

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.