Performance Analysis of Algorithm
The Efficiency of an Algorithm can be measured by the following metrics.
- Time Complexity and
- Space Complexity.
1. Time Complexity:
The amount of time required for an algorithm to complete its execution is its time complexity. An algorithm is said to be efficient if it takes the minimum (reasonable) amount of time to complete its execution.
The time complexity of an algorithm measures the amount of time taken by an algorithm to run as a function of input.
2. Space Complexity:
The amount of space occupied by an algorithm is known as Space Complexity. An algorithm is said to be efficient if it occupies less space and required the minimum amount of time to complete its execution.
The space complexity of an algorithm measures the amount of space taken by an algorithm to run as function of input.
Types of Analysis
Worst Case Running Time:
The worst case running time of an algorithm is an upper bound on the running time for any input. Knowing it gives us a guarantee that the algorithm will never take any longer.
For expressing worst case running time of an algorithm Big O notation is used.
Best Case Running Time:
The best case running time of an algorithm is lower bound on the running time for any input. The best rarely occurs in practice.
For expressing best case running time of an algorithm Big Ω notation is used.
Average Case Running Time:
The average case running time of an algorithm is an estimate of the running time for an “average input”.
For expressing, average case running time of an algorithm Big Ɵ notation is used.
Amortized Analysis:
In amortized analysis, the time required to perform a sequence of (related) operations is averaged over all the operations performed. Amortized analysis is concerned with the overall cost of arbitrary sequences.
It is the average performance of each operation in the worst case. It guarantees the average performance of each operation in the worst case.
Amortized analysis can be used to show that the average cost of an operation is small, if one averages over a sequence of operations, even though a simple operation might be expensive.