Best / Worst / Average Case Analysis

1// LINEAR SEARCH — All three cases
2function linearSearch(arr, target) {
3  for (let i = 0; i < arr.length; i++) {
4    if (arr[i] === target) return i;
5  }
6  return -1;
7}
8// Best case:  O(1)   — target is first element
9// Worst case: O(n)   — target is last or not present
10// Average:    O(n/2) = O(n) — on average, check half the array
11
12// QUICKSORT — Average vs Worst case
13function quickSort(arr) {
14  if (arr.length <= 1) return arr;
15  const pivot = arr[arr.length - 1];
16  const left = [], right = [];
17  for (let i = 0; i < arr.length - 1; i++) {
18    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
19  }
20  return [...quickSort(left), pivot, ...quickSort(right)];
21}
22// Best/Avg:  O(n log n) — balanced partitions
23// Worst:     O(n²)      — already sorted + last element as pivot!
24
25// BINARY SEARCH — Best vs Worst
26function binarySearch(arr, target) {
27  let lo = 0, hi = arr.length - 1;
28  while (lo <= hi) {
29    const mid = (lo + hi) >>> 1;
30    if (arr[mid] === target) return mid;   // Best: O(1) — found at mid
31    arr[mid] < target ? lo = mid + 1 : hi = mid - 1;
32  }
33  return -1;
34}
35// Best:  O(1)      — target is at middle
36// Worst: O(log n)  — target at extremes or absent
37
38// INSERTION SORT — Shows all three cases clearly
39function insertionSort(arr: number[]): number[] {
40  for (let i = 1; i < arr.length; i++) {
41    const key = arr[i];
42    let j = i - 1;
43    while (j >= 0 && arr[j] > key) {
44      arr[j + 1] = arr[j];
45      j--;
46    }
47    arr[j + 1] = key;
48  }
49  return arr;
50}
51// Best:  O(n)   — already sorted (inner loop never runs)
52// Worst: O(n²)  — reverse sorted (inner loop runs max)
53// Avg:   O(n²)  — random order