Engineer bro!
Wed Apr 13 2022 (1 year ago)
Engineer by mistake!
I am a software engineer by passion
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.
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.
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.
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.
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.
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.
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.
© 2021 dsabyte. All rights reserved