The problem is as follows:
The input is an array $A$ of $n$ natural numbers such that:
(1) if the maximum occurs in $A[p]$ for an index $p$, then $$A \leq \ldots \leq A[p-1] \leq A[p]$$ and $$A[p] \geq A[p+1] \ldots \geq A[n];$$
(2) if $A[i]=A[j]=x$ then $A[k]=x$ for $i \leq k \leq j$.
The goal is to find the maximum element of $A$. Restriction (2) imposes the additional difficulty that $A$ might contain plateaus, and hence a simple binary search does not work. I came up with the following algorithm, but I'm having a hard time analyzing its time complexity.
// p is start index and q the ending index (inclusive) FindPeak(A, p, q) 1 if q - p = 0 then return p 2 m = (p + q) / 2 // assume that the division applies the floor 3 i = FindPeak(A, p, m) 4 j = FindPeak(A, m + 1, q) 5 if A[i] = A[j] then // A[i..j] is a plateau 6 i = FindPeak(A, p, i) 7 j = FindPeak(A, j, q) 8 if A[i] < A[j] then return FindPeak(A, j, q) 9 else return FindPeak(A, p, i)
Let $n=q-p$ and $T(n)$ be the function describing the running time of
I know that lines 3 and 4 are $T(n/2)$ each, but I'm not sure about lines 6 through 9. Could you help me constructing the recurrence relation for $T(n)$? (And any eventual bug that might be lurking there.)
PS 1. If the entire array is a plateau (all the elements are equal), then is it correct to say that the worst-case running time of
FindPeak is $\Omega(n)$?
PS 2. After reading a comment, I realized that I didn't understand the problem properly. The simplified algorithm is as follows:
// p is start index and q the ending index (inclusive) FindPeak(A, p, q) 1 if q - p = 0 or A[p] = A[q] then 2 return p 2 m = (p + q) / 2 // assume that the division applies the floor 3 i = FindPeak(A, p, m) 4 j = FindPeak(A, m + 1, q) 5 if A[i] < A[j] then 6 return FindPeak(A, j, q) 7 else 8 return FindPeak(A, p, i)
I still have trouble to analyze the time complexity because of lines 5 through 8. Nevertheless, due to lines 3 and 4, I think the running time in the worst-case is at least $\Omega(n)$, right? Is it possible to devise a $O(\log n)$ algorithm?