120 total views

Performance analysis of an algorithm is done to understand how efficient that algorithm is compared to another algorithm that solves the same computational problem. Choosing efficient algorithms means computer programmers can write better and efficient programs.

A computer resource is **memory** and **CPU time** and performance analysis revolves around these two resources. Two ways to evaluate an algorithm is listed below.

- Space requirement
- Computation time

### Space Complexity

The space requirement is related to memory resource needed by the algorithm to solve a computational problem to completion. The program source code has many types of variables and their memory requirements are different. So, you can divide the space requirement into two parts.

**Fixed Variables**

The fixed part of the program are the instructions, simple variables, constants that does not need much memory and they do not change during execution. They are free from the characteristics of an instance of the computational problem.

**Dynamic Variables**

The variables depends on input size, pointers that refers to other variables dynamically, stack space for recursion are some example. This type of memory requirement changes with instance of the problem and depends on the instance characteristics. It is given by the following equation.

\begin{aligned}&S(P) = c + SP \\ &where \\ &S(P) \hspace{1mm} is \hspace{1mm}space\hspace{1mm} requirement\\ &c \hspace{1mm}is\hspace{1mm} a \hspace{1mm}constant \\ &SP\hspace{1mm} is\hspace{1mm} the \hspace{1mm}instance \hspace{1mm}characteristics \end{aligned}

**Instance characteristics** means that it cannot be determined unless the instance of a problem is running which is related to dynamic memory space. The** input size** usually has the control over instance of a computational problem.

### Time Complexity

The time complexity is the amount of time required to run the program to completion.It is given by following.

\begin{aligned}&T(P) \hspace{1mm} = compile \hspace{1mm}time\hspace{1mm} +\hspace{1mm} run-time\\ &P\hspace{1mm} is \hspace{1mm}the \hspace{1mm}program.\\ &T(P) \hspace{1mm}is \hspace{1mm}the \hspace{1mm}time\hspace{1mm} complexity \hspace{1mm}of \hspace{1mm}program.\end{aligned}

**Program Execution in Steps**

The computer executes a program in steps and each step has a time cost associated with it. It means that a step could be done in finite amount of time.See the table below.

Program Step | Step Value | Description |

Comments | zero | comments are not executed |

Assignments | 1 step | can be done in constant time |

Arithmetic Operations | 1 step | con be done in constant time |

Loops | Count Steps | if loop runs n times, count step as n+1 and any assignment inside loop is counted as n step. |

Flow Control | 1 step | only take account of part that was executed. |

You can count the number of steps an algorithm performed using this technique.

For example, consider the following example.

Operations | S/e | Frequency | Total Steps |

Algorithm Sum(a, n) | 0 | – | 0 |

{ | 0 | – | 0 |

s:= 0; | 1 | 1 | 1 |

for i:= 1 to n do | 1 | n + 1 | n + 1 |

s:= s + a[i]; | 1 | n | n |

return s; | 1 | 1 | 1 |

} | 0 | – | 0 |

Total | 2n + 3 |

Note:-

\begin{aligned}& S/e = steps \hspace{1mm}per \hspace{1mm} execution\hspace{1mm} of\hspace{1mm} a \hspace{1mm}statement.\\ &Frequency = The\hspace{1mm} number\hspace{1mm} of\hspace{1mm} times \hspace{1mm}a \hspace{1mm}statement \hspace{1mm}is \hspace{1mm}executed. \end{aligned}

The result of the step count is which is a linear function. The performance analysis begins by counting the steps, but count the steps to execute is not the goal. The goal is to find a function that will describe the algorithm in terms of its input size. This function will tell you how the algorithm will perform for different input size and magnitude.

Bestseller

**Introduction to Algorithms, 3rd Edition (The MIT Press) 3rd Edition**

Best book for students with little programming experience. The algorithms are designed and explained in easy to understand manner. The book includes many exercises and problems. The text is intended primarily for students studying algorithms or data structures. As it discusses engineering issues in algorithm design, as well as mathematical aspects, it is equally well suited for self-study by technical professionals.