# What recurrence describes the time complexity of this algorithm?

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 FindPeak. 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?

• Your ps is incorrect. If the first and last values are the same, those are maximum, so in that case you have constant time. Note that the same value cannot appear on different sides of the max. Apr 1 at 18:05
• The way I wrote, the behavior you describe is not clear for me. Should I add this test, say, after line 1? That is, if A has more than 1 element, than I check if the first and last are the same. If they are, okay, they are maximum. Otherwise, search in each halve recursively. Is that it? Apr 1 at 18:38
• No wait, your comment made me realize that I may not have understood the problem properly. For instance, A=[1,2,3,2,2] would not be a valid input because that 3 violates condition (2), right? Geez.. then I think that algorithm is not good. :( Apr 1 at 18:48
• It seems that input is ruled out by Restriction (2), yes. Apr 1 at 21:26
• What if you check 4 values, the first, the 1/3, 2/3 and the last. Then you have 3 segments. Can you discard one of them? Apr 1 at 21:32

Partial answer: The problem admits an $$O(n^{\log_3(2)}) \leq O(n^{0.631})$$ algorithm.

The algorithm $$\mathcal A$$ works as follows:

1. Query $$x = A[n/3]$$ and $$y = A[2n/3]$$.
2. If $$x = y$$, return $$\max \{x, \mathcal A(A[1, n/3]), \mathcal A(A[2n/3, n])\}$$
3. If $$x < y$$, return $$\max \{\mathcal A(A[n/3, 2n/3]), \mathcal A(A[2n/3, n])\}$$
4. If $$x > y$$, return $$\max \{\mathcal A(A[1, n/3]), \mathcal A(A[n/3, 2n/3])\}$$

($$A[p, q]$$ denotes the sub-array of $$A$$ starting at index $$p$$ and ending at index $$q$$.)

It should be easy to see that $$\mathcal A$$ works correctly. The running time $$T(n)$$ of $$\mathcal A$$ is given by $$T(n) = O(1) + 2 \cdot T(n / 3)$$, which solves to $$T(n) = O(n^{\log_3(2)})$$.

• I arrived at that solution with minor differences. But isn't the solution to the recurrence $\Theta(n^{\log_{3}2})$? Apr 1 at 22:57
• Why would it be? Intuitively, every recursive step reduces the size of the remaining instance by a factor of $2/3$, so we arrive at a constant-size instance after $\log_{3/2}(n) = O(\log n)$ steps. Apr 2 at 8:12
• I think your reasoning would be correct if the recurrence was $T(n)=T(2n/3)+O(1)$. But for $T(n)=2T(n/3)+O(1)$, we always divide the input by 3, so the recursion tree of $T(n)$ has height $\log_{3}n$. But each level $i$ has $2^i$ nodes (since we do two recursive calls), each "costing" $O(1)$. Summing all the nodes, we end up with $T(n)=\sum_{i=0}^{\log_{3}n}2^ic$ ($c$ is the hidden constant of $O(1)$). Applying the formula for a geometric series, this will result in $\Theta(n^{\log_{3}2})$. Apr 2 at 19:48
• Whoops, you're right. I'll edit the post accordingly. Apr 4 at 19:23