CODEWITHSUNDEEP
algorithm
user2718830
user2718830

Reputation: 53

Optimized algorithm to find all the local maximum

I am currently looking into the time complexity of the algorithm for finding all the local maxima. According to this, the time complexity is O(log N) for 1D array. Is it for finding out only one maxima?

What if I want to find all the maxima? Is there any way to find all of them with complexity smaller than O(N) of brute force method?

Thank you.

Upvotes: 1

Views: 4532

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65458

amit's lower bound is correct but not as interesting as it could be, since the instances under consideration may have Omega(n) local maxima.

It turns out that, in the randomized cell-probe model of computation versus an oblivious adversary, even finding a second local maximum requires Omega(n) probes in expectation. Start with the array 1..n and choose one of the elements uniformly at random to be increased by 2. This makes a second local maximum (unless the last element is selected), with the first, of course, being the last element of the array. The algorithm does not learn anything about the location of the second local maximum until it probes the perturbed location. By Yao's lemma, some deterministic algorithm is optimal against this oblivious adversary, so the expected time to find the second local maximum is at least (n + 1)/2 probes.

Upvotes: 1

amit
amit

Reputation: 178431

As I stated in comments, for the counter example of [1,2,1,2,...] there are O(n) local maxima, and the output size itself is thus O(n).

Another approach to prove that finding all local maxima is Omega(n) problem, goes as folloes.

First, note that finding global maximum is Omega(n) problem.
Now, we will represent the following algorithm to solve global maximum in an array A:

  1. Find all local maxima in A
  2. Regard the elements found in (1) as the new array A.
  3. if size(A) > 1 - return to 1
  4. else: the only element in A is the global maxima.

Correctness of the algorithm is pretty trivial, we iteratively discard elements, and the global maximum is never discarded.

Complexity:

  • Note that in each step, at least size(A)/2 elements are removed (why?)
  • This gives us the complexity of O(d(n)) + O(d(n/2)) + O(d(n/4)) + ... + O(d(1))
  • In the above O(d(n)) is the complexity of the optimal 'find all local maxima' algorithm (step 1).
  • Now, given this fact, and assuming (towards contradiction) d(n) is in o(n) [small o notation, d(n) is asymptotically 'weaker' than n)] - we get that d(n) + d(n/2) + ... + d(1) is in o(n + n/2 + ... + 1) = o(2n) = o(n)

So, we solved global maximum in o(n) algorithm, but it is Omega(n) problem - contradiction.
Thus, the algorithm in step 1 MUST be Omega(n).

Upvotes: 3

Related Questions