Peak Finding

If we have a function \(f(x)\) and we want to find the global maximum and local maximum, how do we do it?

In many cases, finding the local maximum is a good enough solution and is generally a lot faster to find.

Global maximum time complexity

// assume unsorted array A[0..n-1]
int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

To find global maximum, the time complexity will be \(O(n)\). This is too slow!

Local Maximum

Finding a local maximum means we want to find some element in array A such that A[i - 1] <= A[i] and A[i + 1] <= A[i]. In other words, this element is greater than both its neighbours.

Let's try to explore some algorithms to find the local maximum. Harnessing the power of reduce-and-conquer, we will start from the middle and recurse.

here, we arrive at the following algorithm

findPeak(int[] arr, int n) {  // where n is size of array
    if (arr[mid + 1] > arr[mid]) {
        return findPeak(A[mid + 1 ...n], n/2)
    } else if (arr[mid - 1] > arr[mid]) {
        return findPeak(A[0..mid - 1], n/2)
    } else { // n / 2 is peak
        return n / 2
    }
}

Invariant

To explore why this works, we can look at the invaraint:

If we recurse on the either half, then there exists a peak in that half.

In our earlier example, if we recurse on the right half, then there exists a peak in the right half. To support this, we will proof by contradiction.

Proof by Contradiction

1. Assume there is no peak in the right half.
2. A[mid] < A[mid + 1] (given)
3. Since there are no peaks, A[mid + 1] < A[mid + 2] (else A[mid + 1] is a peak)
4. Since there are no peaks, A[mid + 2] < A[mid + 3] (else A[mid + 2] is a peak)
5. By induction, A[j - 2] < A[j - 1] for all j > mid
6. Since there are no peaks, A[n - 2] < A[n - 1]
7. But A[n - 1] is the last element of the array, making it a peak.
8. This contradicts 1 that assumes there is no peak, making it false.

Note this may not follow the proper proof format but is mainly for the idea. The following diagram also illustrates this:

Another way of phrasing that invariant is basically

There exists a peak in the range [begin, end].

But is this sufficient to show that our algorithm is correct? Well, unfortunately not. We also have to specify the following:

Every peak in the range [begin, end] is a peak in [0..n-1].

Insufficient invariant

Hopefully this diagram illustrates why the second part has to be added.

In this scenario, [begin, end] could mean the middle of the array in which case 15 is no longer a peak in the actual array.

Another invariant we have is:

If we recurse on the right half, then every peak in the right half is a peak in the array.

Running TIme

To analyse the running time, we have \(T(n) = T(n / 2) + Θ(1)\) where

• \(T(n)\) : Time to find a peak in array of size n
• \(T(n / 2)\) : Time taken for recursion
• \(Θ(1)\) : Time for comparing A[n / 2] with neighbours

Unrolling the recurrence, we get

\(T(n) = Θ(1) + Θ(1) + ... + Θ(1) = O(log n)\)

Unrolling the Recurrence

\(T(n) = T(n / 2) + Θ(1)\)

\(= T(n / 4) + Θ(1) + Θ(1)\)

\(= T(n / 8) + Θ(1) + Θ(1) + Θ(1)\)

\(..\)

\(= T(1) + Θ(1) + ... + Θ(1)\)

\(= Θ(1) +Θ(1) + ... + Θ(1)\)

\(= O(log n)\)

Note that the number of times you can divide n by 2 until reaching 1 is log(n).

Steep Peaks

The algorithm we found earlier seems like a good solution to finding the peak, but what we have the following array? Which side will the algorithm recurse on?

Using our previous algorithm, we would get 7 since both neighbours are equal to arr[mid]. Maybe we can modify our algorithm a little?

findPeak(int[] arr, int n) {  // where n is size of array
    if (arr[mid - 1] == arr[mid] == arr[mid  + 1]) {
        // recurse on both sides
    } else if (arr[mid + 1] > arr[mid]) {
        return findPeak(A[mid + 1 ...n], n/2)
    } else if (arr[mid - 1] > arr[mid]) {
        return findPeak(A[0..mid - 1], n/2)
    } else { // n / 2 is peak
        return n / 2
    }
}

Running Time

Here, the recurrence runtime will be \(T(n) = 2T(n/2) + O(1)\)

Unrolling the recurrence, we get

\(T(n) = n + n/2 + n/4 + ... + 1 = O(n)\)

Unrolling the Recurrence

\(T(n) = 2T(n/2) + 1\)

\(= 2(2T(n/4) + 1) + 1 = 4T(n/4) + 2 + 1\)

\(= 8T(n/8) + 4 + 2 + 1\)

\(..\)

\(= nT(1) + n/2 + n/4 + n/8 + ... + 1\)

\(= n + n/2 + n/4 + n/8 + ... + 1\)

\(= O(n)\)

As you can see, we end up with a O(n) runtime (i.e. linear time). To keep things simple, once you realize you need linear time, instead of coming up with a complicated algorithm, it will always be good to keep things simple, i.e. just do a linear search a cross the array.

Summary

In summary, for peak finding, the idea behind the algorithm is to use Binary Search where the runtime is \(O(log n)\).