Search for largest element in 1st monotonic subarray with an array consisting of 3 monotonic subarrays

Question

Consider an array A[1..n] that first increases up to some point p then it decreases until some point q and then increases again. That is A[k] < A[k + 1] for all k in [1..p] and [q..n] and A[k] > A[k + 1] if p < k < q.

Suppose we are searching for the element A[p] or the index p, whats the fastest possible algorithms

My Approach: For a similar problem with 2 consecutive monotonically increasing and decreasing arrays you could apply binary search to find the element with the condition A[p]>A[p-1] and A[p+1]. Even though the condition still holds true for 3 consecutive monotonically increasing and decreasing sub arrays, it would not be possible to aim search at left or right from the mid point in a binary search.

A linear search based approach is obvious but is it possible to do this with lesser complexity?

• greybeard: Consider $p+1=q$.

Answer 1

No. It can't be done in sublinear time. I'll prove that any algorithm whose worst-case running time is $n/3-1$ or less, must be incorrect on some input. It follows that every correct algorithm has worst-case running time at least $n/3$, i.e., at least linear.

Consider any deterministic algorithm whose worst-case running time is $n/3-1$ or less. Consider running this algorithm on the array $[1,2,3,\dots,n]$ until termination. Because its worst-case running time is less than $n/3$, it follows that the algorithm examines less than $n/3$ elements of the array. This implies that there must exist three adjacent elements of the array it hasn't looked at, let's call them $A[u]$, $A[u+1]$, and $A[u+2]$. Since the algorithm hasn't looked at them, we can replace the values of those elements arbitrarily, and the algorithm will produce the same output regardless of how we change them. Now consider the two inputs $[1,2,\dots,u,0,u+2,u+3,\dots,n]$ and $[1,2,\dots,u,u+1,0,u+3,\dots,n]$. By the previous remarks, the algorithm yields the same output on both inputs. However, the correct answer for these two inputs is different (the correct answer is $u-1$ for the first and $u$ for the second). It follows that the algorithm produces the wrong output for at least one of these two inputs, i.e., there exists an input where this algorithm is incorrect.

This proof technique is sometimes known as an "adversary argument". We come up with an "adversary" that constructs inputs that the algorithm is sure to handle incorrectly.

• gnasher729: If m is the length of the descending subarray, for some unknown m, then I could see a O(log n + n/m) algorithm possible. But then creating the array will take O(n) anyway, so finding one very specific element in better than O(n) is not very relevant.
• Tassle: You can actually improve the bound to $n-4$. If four indices haven't been looked at, call $u<v$ two of them which are not at the extremities. Then the algorithm can't discriminate between $[1,2,\ldots, u-1,u, u+1, \ldots, v-1, 0, v+1,\ldots n]$ and $[1,2,\ldots, u-1,0, u+1 \ldots, v-1, v, v+1,\ldots n]$. Admittedly this is the same in Landau notation, but still it shows that you can't even save a constant factor.

Answer 2

After some arguments why you can't generally do better:

What if $A[n] \lt A[1]$?
Every element smaller $A[1]$ is to the right of $p$, every element greater $A[n]$ is to the left of $q$.