Why Analysis of the Algorithm?
In this tutorial, we are going to discuss the analysis of the algorithm. Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the required resources of an algorithm to solve a specific computational problem. Analysis of algorithms is the determination of the amount of time and space resources required to execute it.
For example, to go from city “A” to city “B”, there can be many ways of accomplishing this: by flight, by bus, by train and also by bicycle. Depending on the availability and convenience, we choose the one that suits us. Similarly, in computer science, multiple algorithms are available for solving the same problem (for example, a sorting problem has many algorithms, like insertion sort, selection sort, quick sort, and many more). Algorithm analysis helps us to determine which algorithm is most efficient in terms of time and space consumed.
What is the Analysis of the Algorithm
- When we have a problem to solve, there may be several suitable algorithms available. We could obviously like to choose the best.
- Analyzing an algorithm has come to mean predicting the resources that the algorithm requires.
- Generally, by analyzing several candidate algorithms for a problem, the most efficient one can be easily identified.
- Analysis of the Algorithm is required to decide which of the several algorithms is preferable.
- Analysis of the algorithm is required to measure its efficiency of the algorithm.
- The efficiency of an algorithm can be analyzed at two different stages, before implementation, and after implementation.
A Priori Analysis
This is a theoretical analysis of an algorithm. The efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.
A Posterior Analysis
This is an empirical analysis of an algorithm. The selected algorithm is implemented using the programming language. This is then executed on the target computer machine. In this analysis, actual statistics like running time and space required, are collected.
Note
- We will compare algorithms based on their execution time. The efficiency of an algorithm means how fast it runs.
- If we want to measure the amount of storage that an algorithm uses as a function of the size of the instances, there is a natural unit available Bit.
- On the other hand, if we want to measure the efficiency of an algorithm in terms of the time it takes to arrive at the result, there is no obvious choice.
- This problem is solved by the principle of invariance, which states that two different implementations of the same algorithm will not differ in efficiency by more than some multiplicative constant.
- Suppose that the time taken by an algorithm to solve an instance of size n is never more than cn seconds, where c is some suitable constant.
- Practically size of an instance means any integer that in some way measures the number of components in an instance.
- Sorting problem: size is no. of items to be sorted.
- Graph: size is no. of nodes or edges or both involved.
- We say that the algorithm takes a time in the order of n i.e. it is a linear time algorithm.
- If an algorithm never takes more than cn 2 seconds to solve an instance of size n, we say it takes time in the order of cn2 i.e. quadratic time algorithm.
- Polynomial: n power k, Exponential: c power n or n!
The goal of the Analysis of Algorithms
The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of running time but also in terms of other factors (e.g., memory, developer effort, etc.)
That’s all about the Analysis of the Algorithm. If you have any queries or feedback, please write us email at contact@waytoeasylearn.com. Enjoy learning, Enjoy Data Structures.!!