Counting Operations and Best, Worst and Average Cases

One algorithm, several behaviours

To analyse an algorithm, count how many times its basic operations run as a function of n. Statements that run once cost a constant; a loop that runs n times multiplies its body's cost by n. Often the count depends on the particular input, not just its size, so we distinguish cases. The worst case is the maximum work over all inputs of size n: for linear search, the target is last or absent, so n comparisons. The best case is the minimum: the target is first, so 1 comparison. The average case is the expected work under some assumption about inputs: if the target is equally likely to be anywhere, about n/2 comparisons. Worst-case analysis is the most common because it gives a guarantee and does not depend on assumptions about input distributions. Average-case analysis matters for algorithms like quicksort and hash tables, whose typical behaviour is much better than their worst case.

Linear search with its operation counts

The number of comparisons depends on where (or whether) the target appears.

def linear_search(items, target):
    for i, x in enumerate(items):   # runs up to n times
        if x == target:             # 1 comparison per iteration
            return i
    return -1

# best case:    target at index 0        -> 1 comparison
# worst case:   target absent or last    -> n comparisons
# average case: target equally likely at any index -> about n / 2 comparisons
# all three grow linearly with n except the best case, which is constant

Looking for your keys

Searching pockets one by one: best case they are in the first pocket, worst case in the last (or not on you at all), and on an average day somewhere in the middle. You plan your morning around the worst case if you cannot be late.

त्वरित जाँच: For linear search on an array of n elements, what is the worst-case number of comparisons?

• 1
• log n
• n²
• n