Asymptotic Notation: Big-O, Big-Omega, Big-Theta

Introduction

When analyzing algorithms, it is not practical to describe performance using exact counts of operations. These counts can vary depending on implementation details and are often too complex to compute precisely. In this context, exact values are not required when comparing how algorithms scale with input size.

To address this, we use asymptotic notation, a mathematical tool that describes how an algorithm’s performance grows with input size. Instead of focusing on exact numbers, asymptotic notation captures the overall trend or growth rate. This allows different algorithms to be compared in a consistent and meaningful way, regardless of the environment in which they run.

Why asymptotic notation is needed

Consider an algorithm whose running time can be expressed as:

This expression gives a detailed count of operations, but it is not very useful for comparison. As the input size increases, the term $n^2$ grows much faster than the other terms. For large values of $n$, the smaller terms and constant factors have very little impact on the overall performance.

This observation leads to an important idea:

• The dominant term determines how an algorithm grows.

• Constants and smaller terms become less significant as $n$ increases.

Asymptotic notation captures this idea by focusing only on the most important part of the growth.

Big-O notation

Big-O notation is used to describe the upper bound of an algorithm’s running time. It represents the maximum amount of work an algorithm might perform as the input size grows.

In simple terms, Big-O answers the question:

How does the running time grow in the worst case?

So far, we have described time complexity informally. To make this precise, we define Big-O using a mathematical relationship between functions.

A function $f(n)$ is said to be $O(g(n))$ if there exist positive constants $c$ and $n_0$​ such that:

This definition means that beyond some input size $n_0$ ...