Best, worst and average case

The cost of an algorithm depends on the input, not only on its size: best case, worst case and average case, for the searches and sorts of the path.

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

Best case: what is it?
Show the answer
The input of size n for which the algorithm runs the fewest operations.
For linear search, it is the value in the first cell: 1 comparison, whatever n is.
How many shifts does insertion sort make on the array [6, 5, 4, 3, 2, 1]?
- 15
- 5
- 6
- 21
Show the answer
15
Each element has to move past all those before it: 1 + 2 + 3 + 4 + 5 = 15 shifts. This is the worst case for 6 values. 5 would be the number of comparisons on an already sorted array.
For linear search, the best case costs … comparison (value in the first cell) and the worst case costs … comparisons (value absent or in the last cell).
Show the answer
For linear search, the best case costs 1 comparison (value in the first cell) and the worst case costs n comparisons (value absent or in the last cell).
Both depend on the input, not only on n. The size of the array is the same, 100 for instance, in both cases.
Worst case: what is it?
Show the answer
The input of size n for which the algorithm runs the most operations; its cost bounds that of all the other inputs of the same size.
For linear search, it is a value that is absent or in the last cell: n comparisons. You can guarantee “never more than this”.