To go from city ‘A’ to city ‘B’ there can be many ways of accomplishing this: by bus, train and also bt the bicycle. Depending upon the availability and convenience, we chose the one that suits us. Similarly, in computer science, multiple algorithms is available for solving a problem. Algorithm analysis helps us to determine which algorithm is most efficient in term of time and space consumed .
The goal of analysis of algorithm is compare algorithms mainly in term of running time but also in terms of other factors (eg: memory, developer effort, etc.)
Running time analysis
It is the process of determining how processing time increase as the size of problem (input size) increases. Input size is the number of element in the input and depending on the problem type, the input may be of different types. The following types of inputs.
- Size of an array
- Polynomial degree
- Number of element in a matrix
- Number of bits in the binary representation of input
- Vertices and edges in a graph
Comparison of algorithm
To compare algorithm, lets us define a few objective measures:
Execution times ? Not a good measure as execution times are specific to a particular computer.
Number of statement executed ? Not a good measure , since the number of statements varies with the programming language as well as the cycle of the individual programmer.
Ideal solution ? Let us assume that we express the running time of given algorithm as a function of the input size n (i.e.,f(n)) and compare these different functions corresponding to running times. This kind of comparison is independent of machine time, programming style.
Lets take example :
we need to boil eggs, we need following steps
- Take half of the water in cookware
- Take some egges.
- Put egges in cookware
- while(egges are boiled)
- closed the cookware
- fire up gasstove
To analysis the above mentioned algorithm to cook eggs , we are calculate number of sets , total time take by computer to process this steps and memory consumption.
Hence, analysis of algorithm is important in machine learning to optimize the processing of data.