0
$\begingroup$

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[1] \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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – John Kemeny
    Commented Apr 1, 2023 at 18:05
  • $\begingroup$ 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? $\endgroup$
    – Lucas Peres
    Commented Apr 1, 2023 at 18:38
  • $\begingroup$ 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. :( $\endgroup$
    – Lucas Peres
    Commented Apr 1, 2023 at 18:48
  • $\begingroup$ It seems that input is ruled out by Restriction (2), yes. $\endgroup$
    – John Kemeny
    Commented Apr 1, 2023 at 21:26
  • 1
    $\begingroup$ 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? $\endgroup$
    – John Kemeny
    Commented Apr 1, 2023 at 21:32

1 Answer 1

Reset to default
2
$\begingroup$

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)})$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I arrived at that solution with minor differences. But isn't the solution to the recurrence $\Theta(n^{\log_{3}2})$? $\endgroup$
    – Lucas Peres
    Commented Apr 1, 2023 at 22:57
  • $\begingroup$ 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. $\endgroup$
    – Watercrystal
    Commented Apr 2, 2023 at 8:12
  • 2
    $\begingroup$ 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})$. $\endgroup$
    – Lucas Peres
    Commented Apr 2, 2023 at 19:48
  • 1
    $\begingroup$ Whoops, you're right. I'll edit the post accordingly. $\endgroup$
    – Watercrystal
    Commented Apr 4, 2023 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.