Same Algorithm, Different Performance? | Best, Average, Worst Case Explained

You wrote an algorithm… and it works perfectly

But sometimes it runs fast…
and sometimes it becomes slow

Why does this happen?

Because algorithm performance depends on the input case

Three Types of Cases
Best Case

• Fastest possible scenario
• Example: target found at first index
• Time: O(1)

Average Case

• Typical scenario across all inputs
• Expected performance
• Time: O(n)

Worst Case

• Slowest possible scenario
• Example: element not found or at last index
• Time: O(n)

Example: Linear Search

int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}

Case Analysis

• Best Case → element at index 0 → O(1)
• Worst Case → element not found → O(n)
• Average Case → ~n/2 comparisons → O(n)

Why Do We Focus on Worst Case?

Because it gives a guarantee:

“Algorithm will NEVER take more than this time”

This is critical for:

• Large-scale systems
• Real-time applications
• Performance-sensitive code

For More: https://www.quipoin.com/tutorial/data-structure-with-java/best-average-worst-case