Average Case Time Complexity

For problem where we have a distribution over our data, we can make use of the average case. And this is related to the knowledge of statistics.

For example, suppose we have an array of size n, and we want to search x in this array. We assume that x is in the array and it is there exactly once. And we use linear search to do the job:

int linear_search(int[] arr, int x) {
    int len = arr.length;
    
    for (int i = 0; i< len; i++) {
        if(arr[i] == x) {
            return i;
        }
    }
    return -1;
}

• Worst Case: x is at the end of the array => we need to traverse n elements.
• Best Case: x is at the beginning of the array => we only compare with the first one.

What is the average case?

Suppose P(i) denotes the likelihood (or probability) that x is stored on the ith position, and we have a distribution like this:

i	1	2	3	…	n
P(i)	P(1)	P(2)	P(3)	…	P(n)

If x is stored at the ith position, we need to traverse i times. Therefore, if we know the above distribution, we can calculate the mathematical expectation of the number of traverse.

The expected number of traverse is:

1 * P(1) + 2 * P(2) + ... + n * P(n)

Therefore our average case time complexity is O(Σ(iP(i))).

In many algorithmic problems, we do not really know what our distribution is. And in those scenarios, we’ll be using the worst case.