Analysis of algorithm

Algorithm : an algorithm is the step by step instructions to solve any given problem.

Let Us now understand this simple algorithm.

Example : sum(n) Algorithm to add first n natural numbers. Assuming s is a variable initialized to 0.

Step 1: if n<=0

return -1;

Step 2: repeat step 3 and step 4 while n!=0

Step 3: s = s + n;

Step 4: [ decrement n ] n--;

Step 5: return s;

As we have discussed above the algorithm is a step by step instructions to solve any given problem but if we came to a situation where we have many algorithms to solve a given problem then we have to decide which one is the suitable in terms of time and space complexity.

Analysis of algorithm: The goal of the analysis of algorithm is to compare algorithms mainly in terms of running time but also in terms other factors ( like memory, efforts etc).

Rate of growth :

The rate at which the running time increases as a function of input is called rate of growth.

Example:-

f(n) = n^4 + 2n^2 + 100n + 500
f(n) = n^4 for some n>n0.

Note: always highest degree of n is considered.

Type of analysis:

To analyze the given algorithm we need to know on what inputs the algorithm is taking less time and on what input the algorithm is taking more time.

We can justify the time in three cases :-

Worst case.
Average case.
Best case.

Analysis of algorithm - Data Structure