Analysis of the Algorithm

The analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them.

Usually, this involves determining a function that relates the size of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small or grow slowly compared to a growth in the size of the input. Different inputs of the same size may cause the algorithm to have different behaviour, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst-case inputs to the algorithm.

Types of Algorithm analysis

There are mainly two types of analysis

• Empirical - Run the Algorithm and measure how much processor time and storage are needed.

• Theoretical - Mathematically computing how much time and space are needed as a function of input size.

Empirical (posteriori) approach

Suppose we want to compare two sorting algorithms (1) Bubble sort and (2) Merge sort. As we have seen in the previous article, both algorithms take different amount of time and space while executing. With Empirical approach, we need to run both algorithms on a physical computer and compare the amount of time and space needed.

Disadvantage of Empirical approach

There are many disadvantages of the Empirical approach, let's discuss them one by one.

• Implementation of different techniques may be difficult

• The same hardware and software(OS) must be used for comparing two algorithms.

• Time is required to compare algorithms, as we have to prepare for a test.

• Result may not be indicative of the running time on other input which was not included in the test.

• Need to test on a different input, for example, consider sorting. First sort 100 numbers, then sort 1k numbers, then 1m and so on.

Theoretical (prior) approach

The theoretical approach involves determining the amount of time and space required by the algorithm by analysing mathematically. The space and time required are calculated on the basis of input size.

The required time is calculated in terms of the number of instructions required to execute and the required space is calculated in terms of the number of storage locations required by the algorithm.

The number of iterations below for the loop will increase by c if we increase n by c, that is:

var n = 5;
for(var i=0; i<n; i++){
    // do nothing for 5 times
}

n	No. of iteration
1	1
5	5
10	10

---

The number of iterations below for the loop will increase by $$(n+c{)}^2-n^2(n+c)^2-n^2$$ if we increase n by c, that is:

n	No. of iterations
2	4
5	25
10	100

var n = 5;
for(var i=0; i<n; i++){ // n times
    for(var j=0; j<n; j++){ // n*n times
        // do nothing
    }
}

Algorithm analysis becomes simple when we consider input size instead of running them on different platforms in an empirical approach.

The important resource needed for an Algorithm

There are two most important resources needed for an algorithm:

• Time - The amount of time the algorithm took to execute

• Space - The amount of space needed by the algorithm during its lifetime.

There are other resources like CPU, network, etc are important. But they are not important to the algorithm, we consider them while implementing the algorithm. Algorithm designing should be separate from its implementation. The implementation of the algorithm could be platform dependednt.

Conslusion

We have seen why algorithm analysis is important and how it can help us to pick the best algorithm candidate. We have also seen the types of algorithm analysis and the resources needed by an algorithm at run time.

I would like to thank you for reading this article.