Analysis of Algorithms. | Priori Analysis | Posterior Analysis


You can find more than one algorithms for solving a particular problem after that you have to analyze them and use the most efficient one. Before going through this article, you must read my post on the Introduction to Algorithms to know what is an algorithm and why it is important. 

How To Analysis an Algorithm?

The analysis of an algorithm is done base on its efficiency. The two important terms used for the analysis of an algorithm is “Priori Analysis” and “Posterior Analysis”.

Priori Analysis: It is done before the actual implementation of the algorithm when the algorithm is written in the general theoretical language. In this, the efficiency of the algorithm is calculated base on its complexity. It is just an approximate analysis.  

Posterior Analysis: It is done after the actual implementation and execution of the algorithm using any programming language like C, C++, Java, or Python. It is the actual analysis in which space and time complexity of the algorithm is calculated more correctly.  

Analysis of Algorithms base on Space and Time Complexity. 

It is difficult to calculate the exact space and running time of all algorithms because it depends on several factors like which language you are using, which compiler, or which machine you are using for the implementation of the algorithm.

Space Complexity: Space complexity is the amount of memory space the algorithm is required for giving the desired output.

Time Complexity: Time complexity is the amount of time required by an algorithm for the execution and providing the desired output.

The time complexity of an algorithm is not measured in time units like seconds or microseconds. It depends on the size of the input, the bigger the size of input more the time an algorithm will take.

We always analyze the algorithm for bigger input because it sometimes it seems similar for smaller input. If the size of the input is n, then f(n) which is a function of n denotes the time complexity.

For example:
The time complexity of a program is given by a function f(n) = 2n^2+2n+1. If we analyze the function for different inputs (n=1, n=10, n=100, n=1000), we can observe the n^2 term more dominant over other terms so we can ignore the smaller terms because it is difficult to calculate the exact function for time complexity.

This method of measuring the approximate complexity is known as asymptotic complexity.  

Next: Introduction to Asymptotic Notations.  

If you like this post and find it useful then you can show your support by donating a small amount from your heart. You can also show your support by following us on Facebook and Twitter. 

Post a Comment

Previous Post Next Post