language agnostic - Peak finding algorithm

Question

I recently started looking at MIT's 6.006 lectures and in the first lecture the instructor presented peak-finding algorithm.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf

According to his definitions:

Given an array [a,b,c,d,e,f,g] where a-g are numbers, b is a peak if and only if a <= b and b>= c.

He gave a recursive approach:

if a[n/2] < a[n/2 -1] then look for a peak from a[1] ... a[n/2 -1]
else if a[n/2] < a[n/2+1] then look for a peak from a[n/2+1] ... a[n]
else a[n/2] is a peak

He said the algorithm is T(n) = T(n/2) + o(1) = o(lgn)

In his pdf he also gave a complete example: [6,7,4,3,2,1,4,5]

Both 7 and 5 are peaks. But doesn't the algorithm above only finds 7 as peak just because the middle element happens to satisfy the first branch?

1. So if we were supposed to find all the peaks, would we still be walking through the entire array? Would it mean worst case N?

2. Does his definition implies we just need to find a single peak?

I believe this problem can be viewed as finding the maximum and minimum element in Riverst's Introduction to Algorithm book.

Answer 1

Yes, this algorithm only finds a single peak.

If you want to find all the peaks you have to check all the elements, so it's going to be O(n).

Note: a peak is not necessarily a global maximum.