Best, Worst, and Average Case

Solution

The best case is the least work the algorithm does on any input of size $n$ . The worst case is the most work it does on any input of size $n$ .

Exercise

Here is a method that returns the index of the first element equal to target, or -1 if there is none. The array is not sorted.

public static int indexOf(int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

Give the best-case time complexity of indexOf and an input that produces it. Then give the worst-case time complexity and an input that produces it.

Solution

Best case is $O (1)$ : target is at index 0, so the first comparison matches and the method returns. Worst case is $O (n)$ : target is not in the array, so the loop compares against all $n$ elements before returning -1.

Exercise

Here is a method that returns the largest value in a non-empty array.

public static int max(int[] arr) {
  int best = arr[0];
  for (int i = 1; i < arr.length; i++) {
    if (arr[i] > best) {
      best = arr[i];
    }
  }
  return best;
}

Give its best-case and worst-case time complexity. Why are they equal, when for indexOf they were not?

Solution

Both are $O (n)$ . There is no early return: the method cannot know best is the maximum until it has compared every element, so it does $n - 1$ comparisons on every input of size $n$ . A best/worst split only exists when the amount of work changes with the input, as it does for indexOf.

Solution

The worst case. The worst case is a guarantee: no input makes the method do more than that. The best case only happens on particular inputs, so it cannot be relied on.

Solution

If target is at position $k$ (counting from $1$ ), the method makes $k$ comparisons. Averaging over the $n$ equally likely positions:

\frac{1 + 2 + \dots + n}{n} = \frac{n ( n + 1 ) /2}{n} = \frac{n + 1}{2}

That is about $n /2$ comparisons, which is $O (n)$ , the same class as the worst case. We need the assumption to define the average. The assumption is a distribution over inputs: target is present and every position is equally likely. Average-case analysis averages over inputs, so it needs one. Worst-case analysis takes the one input that costs the most, so it needs none.

Solution

The array is sorted exactly when no element is larger than the one after it. So we iterate through the adjacent pairs, and as soon as we find a pair that is out of order, we return false.

public static boolean isSorted(int[] arr) {
  for (int i = 1; i < arr.length; i++) {
    if (arr[i - 1] > arr[i]) {
      return false;
    }
  }
  return true;
}

Starting the loop at i = 1 handles the small cases without an extra check: an empty array and a single-element array have no adjacent pairs, so the loop never runs and we return true.

Best case is $O (1)$ : the array starts with a descent, say [5, 1, ...], so the first comparison finds 5 > 1 and the method returns after one comparison, no matter how long the array is. Worst case is $O (n)$ : the array is sorted, so the early return never happens and the method checks all $n - 1$ pairs before returning true.