What you will learn.
What is an Algorithm?
Let us consider the problem of making Tea. To make Tea we need to follow the Below steps:
- Get the vessel.
- Get the milk.
- Do we have milk?
- if yes, put it in the vessel.
- if no, do we want to buy it?
- If yes, go out and buy.
- if no, we can terminate.
- Do we have milk?
- Turn on the stove, etc…
What we are doing is, for a given problem (preparing a Tea), we are providing a step-by-step procedure for solving it. The normal definition of an algorithm can be staled as:
An algorithm is the step-by-step instructions to solve a given problem.
Note: We do not have to prove each step of the algorithm.
Why the Analysis of Algorithms?
To go from city “A” to city “8”, there can be many ways of accomplishing this: by night, 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.
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 lime but also in terms of other factors (e.g., memory, developer effort, etc.)
What is Running Time Analysis?
It is the process of determining how processing time increases as the size of the problem (input size) increases. The input size is the number of elements in the input, and depending on the problem type, the input may be of different types. The following are the common types of inputs.
- Size of an array
- Polynomial degree
- Number of elements in a matrix
- Number of bits in the binary representation of the input
- Vertices and edges in a graph.
How to Compare Algorithms.
To compare algorithms, let us define a few objective measures:
- Execution times? Not a good measure as execution times are specific to a particular computer.
- A number of statements executed? Not a good measure, since the number of statements, varies with the programming language as well as the style of the individual programmer.
- Ideal solution? Let us assume that we express the running time of a 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 Lime, programming style, etc.