Analysis of algorithm depends upon the amount of resources i.e. space and time taken by the algorithm. Space and time complexity depends on lots of factors like hardware, operating system, processors, etc. However, we don't consider any of these factors while analyzing the algorithm. We will only consider the execution time of an algorithm to solve a particular problem.
Space complexity is defined as the amount of space or memory required by the algorithm or the set of code to run until its completion.
Time complexity is defined as the amount of time required by the algorithm or the set of code to run until its completion.
For the analysis of any algorithm, we need to understand for which input the algorithm takes less time and for which input it takes more time, and based on this, we will divide the inputs in three cases:-
The best case time complexity is defined as the minimum amount of time needed by an algorithm for input size n
. It give the lower bound of the running time of the algorithm.
The average case time complexity is defined as the average amount of time needed by an algorithm for all possible inputs.
The worst case time complexity is defined as the maximum amount of time needed by an algorithm for input size n
. It give the upper bound of the running time of the algorithm.