Best, Average, Worst Case
An algorithm's performance can vary depending on the input. We analyze three scenarios:
- Best case – Minimum time (e.g., first element is target).
- Average case – Typical time (expected over all inputs).
- Worst case – Maximum time (e.g., element not found).
Consider linear search on an array of size n:
int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}
- Best case: target at index 0 → O(1)
- Worst case: target not present or at last index → O(n)
- Average case: (n+1)/2 comparisons → O(n)
When we talk about an algorithm's time complexity, we usually refer to the worst case, because it gives the guarantee that the algorithm will never exceed that time.
Two Minute Drill
- Best case: fastest possible (often O(1)).
- Worst case: slowest possible (used as standard).
- Average case: expected time over random inputs.
- Worst-case analysis provides a performance guarantee.
- Important for critical systems.
Need more clarification?
Drop us an email at career@quipoinfotech.com