Worst VS Average

Definition

---

Comparison Table

---

Quick Sort Case Analysis

---

Hash Table Case Analysis

---

BST Case Analysis

---

When to Care About Each Case

---

Code Examples

// Quick Sort with worst case mitigation
public class QuickSort {

    // Bad: Always picks first element (O(n²) on sorted input)
    public void badQuickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = arr[low];  // Bad pivot choice!
            // ...
        }
    }

    // Good: Random pivot (expected O(n log n))
    public void randomizedQuickSort(int[] arr, int low, int high) {
        if (low < high) {
            int randomIndex = low + new Random().nextInt(high - low + 1);
            swap(arr, randomIndex, high);  // Move random to end
            int pi = partition(arr, low, high);
            randomizedQuickSort(arr, low, pi - 1);
            randomizedQuickSort(arr, pi + 1, high);
        }
    }

    // Better: Median-of-three pivot
    public int medianOfThree(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        if (arr[low] > arr[mid]) swap(arr, low, mid);
        if (arr[low] > arr[high]) swap(arr, low, high);
        if (arr[mid] > arr[high]) swap(arr, mid, high);
        return mid;  // Return index of median
    }
}

// BST with worst case consideration
public class TreeChoice {

    // When inputs could be sorted - use balanced tree
    TreeMap<String, Integer> map = new TreeMap<>();  // O(log n) guaranteed

    // When inputs are random - HashMap is fine
    HashMap<String, Integer> fastMap = new HashMap<>();  // O(1) average
}

---

Tips & Tricks

---