Overview
Basically we don’t know about how users provide the input data. So during execution it may impact huge differences in the order of growth.
The order of growth is identified in following ways:
- Best case
- Average Case
- Worst case
Best case
This case is not used because if we’re building a software and if we tell your user in the best cases by saying our software is going to execute it in minimum time and don’t know about the average cases and worst cases then nobody will consider our software is good. So base case scenario is not best fit for us to use.
Average case
Average cases is something which is required due to making certain assumptions about the input or in idle situations required due to knowing the exact input then compute the average. That’s why the average case is also not measured. We don’t know how the user is going to use the function.
Worst case
This case is something that we use the most of the time because in this analysis we are going to determine what will be the input cases which are going to take maximum time or are going to have maximum order of growth.
Sometimes when you write your program and if it doesn’t have any conditions that it’s going to have different order of growth or different cases and in such cases you can see and say one line of order of growth. For example while finding the maximum in an array in that case you will have to traverse the array to find the maximum. There are no best cases, no worse cases and no average cases. It’s like always going to be linear and similarly while finding minimums in the array which is always going to be linear.
Many algorithms have different cases which take different times. There are many standard algorithms also like this: like insertion sort algorithm i.e if you provide sorted input then it takes linear time and if you provide reverse input then it will take quadratic time.
So if algorithms have different times and different order of input then in such a cases we divide the cases in above there cases:
- Best cases: we will know only about the minimum time taken so it is no use.
- Average cases: this is something where you would like to know but impractical many times.
- Worst cases: this is done most of the time, we find out what is the case, input type when this algorithm has maximum order of growth in which we used to indicate that time complexity of the algorithms.
Conclusion
In this post, we learn the three techniques to understand the order of growth of an algorithm.