Algorithmic Time-Complexity Analysis: Asymptotic Notation

Motivation:

When we talk about efficiency of an algorithm, we generally refer to the resources (time, space etc.) that the algorithm will consume for a given input. Especially, we usually are interested in how an algorithm will behave (as in how much time or space will be consumed) for voluminous input size.

A solution to predict the behaviour (say running time) is to come up with a function ƒ(n) that emulates the the time taken by the algorithm  for a given input of size n; it can be done by implementing the algorithm, executing it for different input-sizes while recording the processing-time taken, and plotting a graph (input-size on x-axis and running-time on y axis). A clear disadvantage in this approach is the dependence on too many external factors — programming language used for implementation; computing machine, its architecture and operating system etc. used for execution; how many other programs are running on the same machine while execution; and so on. We would like to abstract the analysis of the algorithm from all these external factors that do not have anything to do with the algorithm itself. Not only that, while comparing the performance of two algorithms so as to choose the better of the two, we do not want interference from any other external factor. Mathematics provides the abstraction technique required while analysing efficiency of an algorithm, namely — Asymptotic Notation.

Asymptotic Notation:

Let us assume that, for an input of size n, the running time of an algorithm is represented by a function T(n). T(n) can be any function but for easy analysis we would like to have running-time expressed in terms of ‘simpler’ functions (whose behaviour we already know) that more or less approximate T(n) to give some sort of ‘guarantees’. Asymptotic notation provides us the bounds of T(n) when n grows towards large value (tends to infinity). 

Mathematical view –

Consider the following graph to grasp the mathematical meaning of the asymptotic notation.

Assuming that f(n) is a simple function ‘known’ to us (e.g. linear, polynomial, exponential, logarithmic etc.) and c is a constant, we can say that for any value of n after n₀, T(n) will never be greater than c.f(n). Simply we can say that T(n) is order of f(n) and write it as follows:

T(n) = O(f(n))

Thus, the O (pronounced big-oh) notation is the formal way of expressing the upper bound of an algorithm’s running time. More formally, for two non-negative functions, T(n) and f(n), if there exists an integer  n₀ and a constant c > 0 such that for all integers n > n₀, T(n) ≤ cf(n), then T(n) is Big O of f(n). This is denoted as T(n) = O(f(n)).

Analogously, we can express the lower bound in terms of big-omega notation.

Here, T(n) and g(n) two non-negative functions and there exists an integer  n₀ and a constant d > 0 such that for all integers n > n₀, T(n) ≥ d.g(n), therefore T(n) = Ω(g(n)).

There is another notation, called theta notation: For non-negative functions, T(n) and f(n), T(n) is theta of f(n) if and only if T(n) = O(f(n)) and T(n) = Ω(f(n)). This is denoted as T(n) = Θ(f(n)). Simply, it implies that T(n) is upper-bounded as well as lower-bounded by the same function.

Note that we should use as tight bound as possible.

Algorithmic View –

Consider an algorithm — linear search — that finds a number in a given array of numbers by looking at each number starting from the first until it finds the number or the array ends. What is the worst case here (i.e. when the algorithm runs longest)? Answer is when the number we are trying to find is the last element of array or it not there at all. Similarly, the best case scenario (i.e. algorithm runs for the shortest time) is when the number is the first element of the array.

The O notation represents the longest running-time of an algorithm for a given input size. In a way, it represents the time taken in the worst case scenarios (that force the algorithm to run the longest).  The  Ω  notation, on the other hand, is to express best case scenarios. For the above mentioned algorithm, assuming that looking at (comparing with) one element of array takes constant time,  running time T(n) is O(n) [it will stop after checking n numbers] and Ω(1) [it will stop after just constant number of operations].

If the algorithm had been designed such that it will go through all numbers of the array even after it has found the given number, then T(n) would have not only been O(n) but also Ω(n). In this case we  would have said T(n) = Θ(n).

A more pedantic way is to see the bounds of the time taken by the algorithm on the worst case input and  the best case input separately. In other words, specifying the O notation and Ω  notation for each — the worst-case input and the best case input –separately. Of course, upper bound of the worst case and the lower bound of the best case will constitute the overall O notation and Ω  notation of the algorithm, respectively. For example, in linear search:
1. The worst case (when the element is not present in the sequence):
upper-bound -> linear (T(n) =O(n))
lower- bound -> linear (T(n) =Ω(n))
Therefore, the worst case time is Θ(n).
2. The best case (when the element is the first in the sequence):
upper-bound -> constant (T(n) =O(1))
lower- bound -> constant (T(n) =Ω(1))
Therefore, the best case time is Θ(1).
But the algorithm, overall, is O(n) and Ω(1).

Calculating the O notation:

The mathematical definition is usually not used to calculate the big-oh notation of some function T(n). There are some simple rules to compute the O notation, given as follows:

1. O(1) is same as some constant c.
2. Multiplication of orders: O(f(n) × O(g(n)) = O(f(n) × g(n)):
   Example – O(n) × O(log n) = O(n × log n)
3. Addition of orders: O(f(n) + O(g(n)) = O(f(n) + g(n)):
   Example – O(log n) + O(log log n) = O(log n + log log n)
4. Ignore the constant terms in a product (i.e. the terms which do not depend on n):
   For example, T(n) = 5 n², then T(n) = O(n²).
5. Ignore the terms with lower growth-rate in a sum of several terms, keeping only the largest growing term:
   T(n) = n³ + n² + 6, then T(n) = O(n³) because n³ is larger growing then the other two terms.

The following table will give an idea of the growth-rate of the most common functions.

Examples:

Linear Search –

Consider the linear search algorithm given above to find the position of a number in an array (and returning NULL if the number is not in the array). We can write it in pseudo-code as

For i from 1 to n:
     If element at position i has the desired value,
         stop the search and return the location (i.e. i);
 Return NULL;

We have been given an array of numbers (say positive), we need to report the maximum sum of a pair of any two numbers in this array. One possible (rather naive) algorithm can be to find sum of all pairs of numbers, keeping track of the maximum sum found until now, so that in the end we have the overall maximum pair-sum.

Initialise SUM to 0;  // variable for keeping the maximum sum 
Initialise tempSUM to 0;   // variable for keeping sum of the current pair
For each i from 1 to n-1:
    For each j from i+1 to n:
        Store sum of numbers at position i and position j in tempSUM;
        If tempSUM > SUM
            SUM = tempSUM;
Return SUM;

If array is empty
    Return NULL;
Else
     Go to middle position; 
     If element at middle position is same as the desired number 
         Return middle;
     Else If element at middle position > the desired number
         Search in the Left half of the array;
     Else
         Search in the Right half of the array;

This is a recursive solution where the size of the array gets halved in each recursive call.  Let’s first calculate how many recursive calls will be there:

1. 0^th call: n
2. 1^st call: n / 2
3. 2^nd call: n / 4
4. 3^rd call: n / 8
5. …
6. i^th call: n / 2ⁱ
7. …
8. last call: 1

If the algorithm makes k calls then (n/2^k)= 1   =>  n =2^k   =>   k = log₂ n.

As calculating middle position and comparison is constant time and there are k (=log₂n) number of calls, we have

T(n) = k × O(1) =  O(log n) × O(1) = O(log n)

Epilogue:

Please pardon the verbosity, oversimplification, and baby-steps. This post is more pertinent to graduate students (who might not have a solid background in either mathematics or programming). It is not intended for a connoisseur of algorithms.🙂

Cheers!