Best, worst and average case

Introduction:

In the field of computer science and programming, analyzing the efficiency of algorithms is crucial. One important aspect of algorithm analysis is understanding the best, worst, and average case scenarios. These scenarios provide insights into the resource usage, such as time complexity or memory usage, for a given algorithm. In this article, we will delve deeper into the concepts of best, worst, and average case analysis and how they impact algorithm performance.

Best Case Scenario:

The best-case scenario represents the minimum resource usage that an algorithm can achieve on a given input. It is the situation where the algorithm performs optimally and requires the fewest number of steps. To illustrate this, let’s consider a simple search algorithm, such as linear search.
In the best case, the element we are searching for is present at the beginning of the list. The algorithm would find the element in the first comparison, resulting in the best possible time complexity – O(1).

Worst Case Scenario:

On the other hand, the worst-case scenario represents the maximum resource usage of an algorithm. It occurs when the algorithm performs the maximum number of steps on a given input. Continuing with our linear search example, the worst-case scenario happens when the element we are searching for is at the end of the list or not present at all.
In this worst-case scenario, the linear search algorithm would iterate through the entire list, resulting in a time complexity of O(n), where n is the size of the input list. Here’s the worst-case implementation for the same algorithm:

Average Case Scenario:

The average case scenario represents the expected or typical resource usage of an algorithm on random input data. It takes into account all possible inputs and provides an average estimate of the algorithm’s performance. To determine the average case, we usually consider the distribution of inputs and calculate the average resource usage.
For certain algorithms, such as quicksort, the average case scenario may have a better time complexity compared to the worst case. Quicksort is a sorting algorithm that divides the input into smaller subproblems. On average, it exhibits a time complexity of O(n log n), which is more efficient than the worst-case time complexity of O(n^2). Here is example implementation of quicksort:

Links

Code Examples

C#
//Best Case Scenario: complexity: O(1)
//LinearSearch Worst Case Scenario: complexity: O(n)
int LinearSearch(int[] arr, int target) {
    for(int i = 0; i < arr.Length; i++) {
        if(arr[i] == target) {
            return i; // element found
        }
    }
    return -1; // element not found
}

//Average Case Scenario: complexity of O(n^2)
void QuickSort(int[] arr, int low, int high) {
    if(low < high) {
        int pivot = Partition(arr, low, high);
        QuickSort(arr, low, pivot - 1);
        QuickSort(arr, pivot + 1, high);
    }
}

int Partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for(int j = low; j < high;
    j++) {
        if(arr[j] < pivot) {
            i++;
            Swap(arr, i, j);
        }
    }

    Swap(arr, i + 1, high);
    return i + 1;
}

void Swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

JavaScript
//Best Case Scenario: complexity: O(1)
//LinearSearch Worst Case Scenario: complexity: O(n)
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // element found
    }
  }
  return -1; // element not found
}

//Average Case Scenario: complexity of O(n^2)
function quickSort(arr, low, high) {
    if (low < high) {
        let pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

function partition(arr, low, high) {
    let pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (arr[j] > pivot) {
            i++;
            swap(arr, i, j);
        }
    }

    swap(arr, i + 1, high);
    return i + 1;
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Python
#Best Case Scenario: complexity: O(1)
#LinearSearch Worst Case Scenario: complexity: O(n)
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # element found
    return -1  # element not found

#Average Case Scenario: complexity of O(n^2)
def quick_sort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quick_sort(arr, low, pivot - 1)
        quick_sort(arr, pivot + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] > pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

PHP
<?php
//Best Case Scenario: complexity: O(1)
//LinearSearch Worst Case Scenario: complexity: O(n)
function linearSearch($arr, $target) {
    for ($i = 0; $i < count($arr); $i++) {
        if ($arr[$i] == $target) {
            return $i; // element found
        }
    }
    return -1; // element not found
}

//Average Case Scenario: complexity of O(n^2)
function quickSort(&$arr, $low, $high) {
    if ($low < $high) {
        $pivot = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot - 1);
        quickSort($arr, $pivot + 1, $high);
    }
}

function partition(&$arr, $low, $high) {
    $pivot = $arr[$high];
    $i = $low - 1;
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            swap($arr, $i, $j);
        }
    }
    swap($arr, $i + 1, $high);
    return $i + 1;
}

function swap(&$arr, $i, $j) {
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

Conclusion