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
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.
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.
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.
S(P) = c + SP where S(P) is space requirement c is a constant SP is the instance characteristics
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.
The time complexity is the amount of time required to run the program to completion.It is given by following.
T(P) = compile time + run-time P is the program. T(P) is the time complexity of the program.
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.
|Algorithm Sum(a, n)||0||–||0|
|for i:= 1 to n do||1||n + 1||n + 1|
|s:= s + a[i];||1||n||n|
|Total||2n + 3|
S/e = steps per execution of a statement.
Frequency = The number of times a statement is executed.
The result of the step count is 2n + 3 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.