Best Worst and Average Case
In this page:
Case Analysis
The same algorithm can take very different amounts of time depending on which specific input it receives, not just the input's size. Analyzing an algorithm properly means looking at more than one scenario instead of assuming performance is the same every run.
Example: Case Analysis
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++)
if (arr[i] == target) return i;
return -1;
}
int main() {
int arr[] = {5, 3, 8, 1, 9};
cout << "Best case (found at 0): " << linearSearch(arr, 5, 5) << endl;
cout << "Worst case (not found): " << linearSearch(arr, 5, 100) << endl;
return 0;
}public class Main {
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++)
if (arr[i] == target) return i;
return -1;
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 1, 9};
System.out.println("Best case (found at 0): " + linearSearch(arr, 5));
System.out.println("Worst case (not found): " + linearSearch(arr, 100));
}
}def linear_search(arr, target):
for i, x in enumerate(arr):
if x == target:
return i
return -1
arr = [5, 3, 8, 1, 9]
print("Best case (found at 0):", linear_search(arr, 5))
print("Worst case (not found):", linear_search(arr, 100))#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++)
if (arr[i] == target) return i;
return -1;
}
int main() {
int arr[] = {5, 3, 8, 1, 9};
printf("Best case (found at 0): %d\n", linearSearch(arr, 5, 5));
printf("Worst case (not found): %d\n", linearSearch(arr, 5, 100));
return 0;
}Login to try C/C++/Java code in the editor
Average Case
Average case describes the expected running time across a realistic mix of inputs, which is often more useful in practice than the absolute best or worst case, but is also harder to calculate because it usually requires assumptions about the input distribution.
Example: Average Case
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 4, 6, 8, 10};
int n = 5;
long totalPositionsChecked = 0;
for (int target = 0; target < n; target++) {
for (int i = 0; i <= target; i++) totalPositionsChecked++;
}
cout << "Average checks per search: " << (double)totalPositionsChecked / n << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int n = 5;
long totalPositionsChecked = 0;
for (int target = 0; target < n; target++)
for (int i = 0; i <= target; i++) totalPositionsChecked++;
System.out.println("Average checks per search: " + ((double) totalPositionsChecked / n));
}
}n = 5
total_positions_checked = sum(i + 1 for target in range(n) for i in range(target + 1))
print("Average checks per search:", total_positions_checked / n)#include <stdio.h>
int main() {
int n = 5;
long totalPositionsChecked = 0;
for (int target = 0; target < n; target++)
for (int i = 0; i <= target; i++) totalPositionsChecked++;
printf("Average checks per search: %.1f\n", (double)totalPositionsChecked / n);
return 0;
}Login to try C/C++/Java code in the editor
Search Example
Linear search is a clean example: in the best case the target is the very first element (O(1)), in the worst case it's the last element or missing entirely (O(n)), and on average, assuming a random position, it examines about half the elements.
Example: Search Example
#include <iostream>
using namespace std;
int main() {
int arr[] = {7, 2, 9, 4, 1};
// Best case: target is arr[0] -> 1 comparison.
// Worst case: target is arr[4] or missing -> 5 comparisons.
cout << "arr[0]=" << arr[0] << " best-case target" << endl;
cout << "arr[4]=" << arr[4] << " worst-case target" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {7, 2, 9, 4, 1};
// Best case: target is arr[0] -> 1 comparison.
// Worst case: target is arr[4] or missing -> 5 comparisons.
System.out.println("arr[0]=" + arr[0] + " best-case target");
System.out.println("arr[4]=" + arr[4] + " worst-case target");
}
}arr = [7, 2, 9, 4, 1]
# Best case: target is arr[0] -> 1 comparison.
# Worst case: target is arr[4] or missing -> 5 comparisons.
print("arr[0]=", arr[0], "best-case target")
print("arr[4]=", arr[4], "worst-case target")#include <stdio.h>
int main() {
int arr[] = {7, 2, 9, 4, 1};
/* Best case: arr[0], 1 comparison. Worst case: arr[4] or missing, 5 comparisons. */
printf("arr[0]=%d best-case target\n", arr[0]);
printf("arr[4]=%d worst-case target\n", arr[4]);
return 0;
}Login to try C/C++/Java code in the editor
Sorting Example
Sorting algorithms are especially sensitive to case analysis. Quicksort runs in O(n log n) on average but degrades to O(n²) in the worst case on already-sorted or adversarial input, which is exactly why picking a good pivot strategy matters.
Example: Sorting Example
#include <iostream>
using namespace std;
int main() {
int sortedArr[] = {1, 2, 3, 4, 5};
// Quicksort on already-sorted input with a bad pivot choice
// degrades from average O(n log n) to worst-case O(n^2).
cout << "sortedArr[0]=" << sortedArr[0] << " (adversarial input for quicksort)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] sortedArr = {1, 2, 3, 4, 5};
// Quicksort on already-sorted input with a bad pivot choice
// degrades from average O(n log n) to worst-case O(n^2).
System.out.println("sortedArr[0]=" + sortedArr[0] + " (adversarial input for quicksort)");
}
}sorted_arr = [1, 2, 3, 4, 5]
# Quicksort on already-sorted input with a bad pivot choice
# degrades from average O(n log n) to worst-case O(n^2).
print("sorted_arr[0]=", sorted_arr[0], "(adversarial input for quicksort)")#include <stdio.h>
int main() {
int sortedArr[] = {1, 2, 3, 4, 5};
/* Quicksort on sorted input with a bad pivot degrades to O(n^2). */
printf("sortedArr[0]=%d (adversarial input for quicksort)\n", sortedArr[0]);
return 0;
}Login to try C/C++/Java code in the editor
Why Cases Matter
Comparing algorithms only by their worst case can be misleading if that worst case rarely happens in practice, and comparing only by best case can hide a real risk. Looking at all three cases together gives a fair, complete picture before you choose an algorithm for production use.
Example: Why Cases Matter
#include <iostream>
using namespace std;
int main() {
// Comparing algorithms fairly means looking at best, worst, AND average --
// not just one case, which can mislead.
cout << "Best: O(1), Average: O(n), Worst: O(n) -- linear search summary" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
// Fair comparison needs best, worst, AND average -- not just one case.
System.out.println("Best: O(1), Average: O(n), Worst: O(n) -- linear search summary");
}
}# Fair comparison needs best, worst, AND average -- not just one case.
print("Best: O(1), Average: O(n), Worst: O(n) -- linear search summary")#include <stdio.h>
int main() {
/* Fair comparison needs best, worst, AND average -- not just one case. */
printf("Best: O(1), Average: O(n), Worst: O(n) -- linear search summary\n");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 6 topics to unlock
0/6 topics done
Complete these topics first: