# Asymptotic analysis 101

## Asymptotic :

The term asymptotic means approaching a value or curve arbitrarily closely (i.e., as some sort of limit is taken). A line or curve a that is asymptotic to given curve c is called the asymptote of c. (http://mathworld.wolfram.com/Asymptotic.html)

When studying Algorithm, even at a beginner level, we need to understand what asymptotic (or limiting) behaviour means. Asymptotic analysis is a way to classify algorithms according to how their running time or space requirements grow. We need to predict how it will behave with a very large amount of data.

# Asymptotic functions

The graph below represents the function f(x)= 1/x. What’s important to observe in this graph is the “tail behaviour”. We are interested in how does f(x) behaves with very large x values :

We can see that where the value of x approach infinity, the output y gets really close to zero. f(x) has a horizontal asymptote at y0 and a vertical asymptote at x→0.

# Asymptotic bounding

## Upper Bound

We use the big O notation to express upper bounding.
If we have the function T(n) that represents the time an algorithm takes :

T(n) is upper bounded by f(n) if and only if T(n)some constant multiplied by f(n) for all n ≥ n, so even when n gets very large.

So, given a function T(n), we can bound it with a function f(n). Let’ s have for example a linear function T(n) and a quadratic f(n) = n². T(n) is upper bounded by as long as we have a constant c that can keep T(n) below at all times. So we can see that we have a large possibility of functions that can upper bound T(n) and we need to know how tight the bound is and chose the tightest one. In this example where T(n) is linear we can also have f(n) = n and find a constant c so that T(n) ≤ cf(n) for all n ≥ n. The Upper bound gives us the order of growth of an algorithm’ s running time in the worst case scenario.

## Lower bound

The function T(n) is lower bounded by f(n) if and only if c*f(n) keeps T(n) above at all times. With linear function T(n), Ω(f(n)) = Ω(log(n)) is an example of lower bounding : T(n) is Ω(f(n)) for all n ≥ n.

## Theta

So we have the upper bound O(.) and the lower bound Ω(.). An exact bound is denoted by theta Θ(.).

O(1)
O(n)
O(log(n))
O(n*log(n))
O(n²)
O(n³)
O(!n)

# Frequency count method :

We can analyse the time and space complexity of an algorithm with the frequency count method. I found really good explanations and examples in this YouTube video by Abdul Bari and I recommend everyone to subscribe to his channel. Here are some examples of O(1), O(n), O(nˣ) Algorithms :

In the case of a simple Swap algorithm where we swap two integers a and b, each statement takes 1 unit of time :

`Swap(a, b){    temp = a;   /* statement takes 1 unit of time */    a = b;      /* statement takes 1 unit of time */    b = temp;   /* statement takes 1 unit of time */}`

T(n) = 3
O(1)

What about space complexity ? We have 3 variables : a, b and temp. Our space function is therefore :

S(n) = 3
O(1)

When a for loop is involved, we need to multiply the repeated statements n times and the loop itself takes n+1 units of time :

`Sum(A, n){    s = 0;                  /* 1 unit of time */    for (i = 0; i < n; i++) /* n+1 unit of time */    {        s = s + A[i];       /* n*1 unit of time */    }    return s;               /* 1 unit of time */}`

T(n) = 2n+ 3
O(n)

We have 4 variables here : A, n, s and i. A takes n units of space and n, s and i take 1 unit of space each.

S(n) = n+3
O(n)

In the case where we have two nested for loop, for example an algorithm that compute the sum of two matrices :

`Add(A, B, n){    for(i = 0; i < n; i++)            /* n+1 */    {        for(j = 0; j < n; j++)        /* n+1 * n */            C[i,j] = A[i,j] + B[i,j]; /* 1 * n * n */        }    }}`

T(n) = 2n² + 2n + 1
O(n²)

We have 6 variables here : A, B, C, n, i and j. A, B, C are n × n matrices and take units of space each and n, i and j take 1 unit of space each.

S(n) = 3n² + 3
O(n²)

An other example :

`Multiply(A, B, n){    for(i = 0; i < n; i++)    {        for(j = 0; j< n; j++)        {            for(k = 0; k< n; k++)            {                C[i,j] = C[i,j] + A[i,k] * B[k,j];            }        }    }}`

T(n) = 2n³ + 3n² + 2n + 1
O(n³)

S(n) = 3n² + 4
O(n²)

--

--

--

## More from Pierre Portal

AI enthusiast 🤖 Software engineer 💻 I share study notes about computer science, AI, deep learning and more. More about my work on www.pierreportal.com

Love podcasts or audiobooks? Learn on the go with our new app.

## Refresh a PowerBI Dataset List using Flow ## Making It Real ## 7 Tips on Upgrading from Drupal 8 to Drupal 9 ## Storage Options in the AWS Cloud: Elastic Block Storage  ## Apache Flex in Action  ## Pierre Portal

AI enthusiast 🤖 Software engineer 💻 I share study notes about computer science, AI, deep learning and more. More about my work on www.pierreportal.com

## Perfect Path For Data Science ## How I Began My Bioinformatics Journey ## Should I learn some data science? 