Asymptotic Notation, It's Greek to Me!
Published: 2022-06-16 12:17:27

Asymptotic analysis, often known as asymptotics, is a way of describing the limiting behavior of a function in mathematics. In computer science, asymptotic analysis is often employed in algorithm analysis. The basic idea is to describe the resource under consideration (typically time, but occasionally memory) as a function with the input size as its parameter. When the values of a function are small or expand slowly in comparison to the size of the input, an algorithm is considered to be efficient. Because different inputs of the same size can lead the algorithm to act differently, <strong>best</strong>, <strong>worst</strong>, and <strong>average</strong> case descriptions may all be informative.

The asymptotic notation consists of a set of operators, expressed as Greek letters. The most significant ones include: <strong>O</strong> (originally an omicron but now typically nicknamed *“Big Oh”*), <strong>Ω</strong> (omega), and <strong>Θ</strong>(theta). The <strong>O</strong> operator definition can serve as a foundation for the other two.The expression O(g), for some function *g*<strong>n</strong>), represents a set of functions, and a function *f*(<strong>n</strong>) is in this set if it satisfies the following condition:
> There exists a natural number <strong>n</strong><subscript>0</subscript> and a positive constant *c* such that:

>>*f*(<strong>n</strong>) £ *cg*(<strong>n</strong>)

> In other words, if we are permitted to change the constant *c* (for example, by running the algorithms on different speeds of machines), the function *g* will ultimately (that is, at <strong>n</strong>0) grow larger than *f*.


## Omega (Ω) Notation

Omega (<strong>Ω</strong>) notation specifies the asymptotic lower bound for a function *f*(<strong>n</strong>). For a given function g(<strong>n</strong>), <strong>Ω</strong>(g(<strong>n</strong>)) is denoted by:
> Ω (g(n)) = {*f*(<strong>n</strong>): there exist positive constants *c* and <strong>n</strong>0 such that 0 ≤ *c* * *g*(<strong>n</strong>) ≤ *f*(<strong>n</strong>) for all <strong>n</strong> ≥ 0}.

This means that, *f*(<strong>n</strong>) = <strong>Ω </strong>(*g*(<strong>n</strong> )), If there are positive constants <strong>n</strong>0 and *c* such that, to the right of <strong>n</strong>0 the *f*(<strong>n</strong>) always lies on or above *c* * *g*(<strong>n</strong>).

## Big – O Notation:

Big – (<strong>O</strong>) notation specifies the asymptotic upper bound for a function *f*(<strong>n</strong>). For a given function *g*(<strong>n</strong>), <strong>O</strong>(*g*(<strong>n</strong>)) is denoted by:

> <strong>Ω</strong> (*g*(<strong>n</strong>)) = {*f*(<strong>n</strong>): there exist positive constants *c* and <strong>n</strong>0 such that *f*(<strong>n</strong>) ≤ *c***g*(<strong>n</strong>) for all <strong>n</strong> ≥ <strong>n</strong>0}. 

This means that, *f*(<strong>n</strong>) = <strong>Ω</strong>(g(<strong>n</strong>)), If there are positive constants <strong>n</strong>0 and *c* such that, to the right of <strong>n</strong>0 the *f*(<strong>n</strong>) always lies on or below *c***g*(<strong>n</strong>).

## Theta (Θ) Notation:

Theta(<strong>Θ</strong>) notation specifies a bound for a function <*f*(<strong>n</strong>). For a given function *g*(<strong>n</strong>), <strong>Θ</strong>(*g*(<strong>n</strong>)) is denoted by:

> <strong>Θ</strong> (*g*(<strong>n</strong>)) = {*f*(<strong>n</strong>): there exist positive constants *c1*, *c2* and <strong>n</strong>0 such that 0 ≤ *c1* * *g*(<strong>n</strong>) ≤ *f*(<strong>n</strong>) ≤ *c2* * *g*(<strong>n</strong>) for all <strong>n</strong> ≥ <strong>n</strong>0}. 

This means that, *f*(<strong>n</strong>) = <strong>Θ</strong>(*g*(<strong>n</strong>)), If there are positive constants <strong>n</strong>0 and *c* such that, to the right of <strong>n</strong>0 the *f*(<strong>n</strong>) always lies on or above *c1* * *g*(<strong>n</strong>) and below *c2* * *g*(<strong>Θ</strong>).

<strong>*Note*</strong> 

- The first two asymptotic operators, <strong>O</strong> and <strong>Ω</strong> , are each other’s inverses: If f is <strong>O</strong>(*g*), then *g* is <strong>Ω</strong> (*f* )

- The <strong>Θ</strong> operator is the most informative of the three.