Time Complexity
The Time Complexity is the important in DSA, because it is used for measure the amount of time an algorithm takes to complete as a function of the length of the input. Time Complexity analysis can be analyzed based on the number of comparisons it makes: –
Best Case
In the Best Case the algorithm makes one comparisons and return immediately, because the target element is at the first position in the list. Thus, time complexity is O (1).
Worst Case
In the Worst Case the algorithm has to compare the target with every element in the list, resulting in n comparison for a list of length n. Because which we target the element it is at last position of the list or is not present in the list at all. Thus, the time complexity is O (n).
Average Case
On Average, the target element might be somewhere in the middle of the list. The algorithm would make n/2 comparisons. However, for asymptotic analysis, constant factors are ignored, so the average case time complexity is also O(n).
Example: –
Suppose we have List: –
[2, 4, 6, 8, 10]- Our First Target is 2; The Algorithm finds the target in the first position, making only one comparison, which make it a Best Case.
- The Second Target is 10; The Algorithm has to traverse all the element to find it. Like if the Target is “11” (which is not present in the list), it will still make five comparisons before concluding the element is absent, which make it Worst Case.
- The Third Target is 6; Here the Algorithm will make around three comparisons (half of the list size for larger lists). Which make it Average Case.