Asymptotic Notation

Asymptotic notation is a common way to describe the behavior of algorithms, or generally just functions. Often times, we will look at the time or space complexity of a function, but it is generally capable of expressing any kind of growth rate of a function.

The reason this is useful is cause it allows us to have a notion of how the performance of an algorithm scales with the size of the input. When it comes to scaling software, we are often interested in how the performance of the system scales with the use. Having an estimation of how the algorithm will scale allows us to make more informed decisions about how to optimize the software, and eventual problems that may arise in the future.

There are a few standard scales that we use to describe growth of rate. To put it into more relatable terms, you can imagine as the growth of some billionaire’s wealth over time. If you have a basic mathematical background, I’m sure you have heard of multiple of these terms before.

• Constant growth: .
• Logarithmic growth: .
• Linear growth: .
• Linearithmic growth: .
• Quadratic growth: .
• Cubic growth: .
• Exponential growth: .
• Factorial growth: .

When using asymptotic notation, we are generally only interested in the largest order of magnitude. For example, if we can express the performance of an algorithm with , we will simply remove the lower order terms, leaving us with . This is because due to the exponential growth, the increase of the smaller term is significantly less important than the increase of the larger term.

Notation

The three common notations used in computer science for describing functions are:

• Big O notation: , expressing the upper bound of the growth rate.
• Big Omega notation: , expressing the lower bound of the growth rate.
• Big Theta notation: , expressing the tightest bound of the growth rate.

At first, it might seem intuitive that the different notations represent best, average, and worst case scenarios. However, this is not the case at all. All three scenarios can often be represented using all three notations.

It helps to think of the notation forms as bounds of a function’s growth. Big O notation simply tells us that nothing will grow faster than noted. Big Omega notation tells us that nothing will grow slower than noted.

As for Big Theta notation, it tells us that the growth rate is asymptotically bound by the function and some constant factor .

In addition, we also have the little variants and . These express strictly lower and strictly higher bounds, respectively. You will most likely not see these very often, but its useful to know that they exist.