Why we do performance analysis?
Analysis of Algorithms-
Two things keep in mind when thinking about an algorithm. First Analysis of algorithm and second design algorithm. Before design the algorithm, we should analyze the algorithm. Analysis of algorithms is the theoretical study of computer program performance and resource usage. How fast an algorithm and Other resources such as memory, communication, etc.
When developing a software, the developer needs to take care of its features like user-friendliness, correctness, simplicity, functionality, modularity, the robustness of software and security etc. Collection of features can be more important than performance. But Performance measures the line between feasible or infeasible. Another reason for studying performance is speed. In short, we can say performance is scale.
Performace Analysis
The performance of an algorithm can be analyzed based on following principles:
Correctness
Simplicity
Optimality
Readability
Time complexity
Space complexity
Correctness:
Simplicity:
Optimality:
Readability:
Space complexity
Space complexity is the amount of space required to solve an algorithm.
The space complexity of a computer program is the amount of memory space required to solve a problem as a function of size of the input.
S(p) =c+sp(i)
where c is a fixed space , which is independent of input and output . It is a constant.
where sp(i) is variable space and it depends on i.
Components of space complexity
There are three components of space complexity:
Instruction or Code Space:
- This space holds the collected version of the program instructions.
Data space:
- This space holds all the static data such as constant, variables and dynamic data such as growing structure.
Environment Stack Space:
- This space is used to store return address for the functions. So that,execution can begin again where they left earlier and it may also be used for parameters.
Example:Recursive function for summing a list of numbers:
float sum(float list[], int n)
{
if (n) return sum(list, n-1) +list(n-1) ;
}
S_{sum}(I)=S_{sum}(n) =6n
Space needed for recursive call of the above program
Type | Name | Number of bytes |
parameter | list[] | 2¹ |
parameter | | 2 |
return address(used internally ) | | 2(unless for address) |
total perrecursive call | | 6 |
Time complexity
Time complexity is the amount of time taken by an algorithm to execute a task.
The time complexity of a program is the amount of time taken to solve a problem or function of size as inputs.
If the time complexity of an algorithm is better, then the algorithm will carry out its work as fast as possible.
Components of Time Complexity
The factors that affects the space complexity also affects time complexity.
The time needed to execute an algorithm depends on several factors.
Usually, it is difficult to find the exact time, so that we approximate the value.
This approximate value can be found by assuming program ‘p’ by taking time is equal to the sum of compile time and run time.
Compile time does not depend on the size of input hence, we will not consider compile-time and hence we will confirm ourselves to consider only the run time which depends on the size of the input.
o Let ‘t_{p}’ be the run time of the program.
o Again, we know that ‘ t_{p}’ depends on several factors. It is difficult to determine the exact value, hence we have to settle for less.
Approximately the ‘ t_{p}’ is given by,
‘t_{p}’(n) =C_{a} ADD(n) + C_{s} SUB(n) + C_{m}MUL(n) +…… ..
Here, n=Size of input
C_{a}=Time needed for addition
C_{s}=Time needed for subtraction
C_{m}=Time needed for multiplication
Hence, we can say that the components of time complexity are operations(addition, subtraction, etc.) performed by processor.
In mathematically, time complexity is expressed as
Time complexity t_{p}(h) =C+ t_{p}(n)
where, C is compile time
t_{p}(n) is runtime.
For example:Recursion function for summing a list of numbers.
float r_{sum}(float list[], int n)
{
if(n) return r_{sum}(list, n-1) +list(n-1) ;
}
S_{sum}(I) =S_{sum}(n) =6n
Speed needed for recursive call of above program.
Type | Name | Number of bytes |
parameter | list[] | 2 |
parameter | | 2 |
return address(used internally ) | | 2(unless for address) |
total perrecursive call | | 6 |
Measures of Time Complexity
Average Case:
- The amount of time the algorithm takes on an average set of inputs.
Worst Case:
- The amount of time the algorithm takes on the worst possible set of inputs.
Best Case:
- The amount of time the algorithm takes on best set of inputs.
Size of Input:
- The running time of a program can be expressed as a function of the size of the input. The size of the input is typically denoted as n and the running time of the algorithm as T(n).
Time Complexity | Example |
| |
1 | Find the 10^{th }elements in an array. |
logn | Binary Search |
nlogn | Merge sort |
n² | Selection sort |
n³ | Matrix multiplication |