Why Analysis of Algorithm ?
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 Analysis of 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, a most efficient one can be easily identified.
- Analysis of Algorithm is required to decide which of the several algorithms is preferable.
- Analysis of algorithm is required to measure the efficiency of algorithm
- 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. 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 programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.
- We will compare algorithms based on their execution time. 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 time it takes to arrive at 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 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!
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.)