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
