Best, Worst, Average and Amortised Cost

1.Average versus worst case

A HashMap lookup is O(1) on average because keys spread across many buckets. If many keys land in the same bucket, lookups slow down; Java turns very crowded buckets into small balanced trees, so the worst case becomes O(log n) rather than O(n). With normal keys, treat it as O(1).

Quick sort is O(n log n) on average but O(n²) in the worst case; merge sort is O(n log n) always. That difference matters when inputs might be adversarial.

2.Amortised: rare expensive steps

An ArrayList stores elements in an array. When it's full, add creates a bigger array (about 1.5× in Java) and copies everything: an O(n) step. But that happens rarely, and the total copying over n adds is still O(n), so each add is O(1) amortised.

public class Main {
    public static void main(String[] args) {
        int capacity = 10, size = 0;
        long copies = 0;
        int n = 1_000_000;
        for (int i = 0; i < n; i++) {
            if (size == capacity) {           // full: grow by 1.5x and copy
                copies += size;
                capacity = capacity + capacity / 2;
            }
            size++;
        }
        System.out.println("adds=" + n + " copies=" + copies + " per add=" + (double) copies / n);
    }
}

adds=1000000 copies=2430972 per add=2.430972