I am currently studying for a test on data structures.
I have to find the lower and upper bounds for the following problem:
An array is called a zigzag array if there are $1 \leq i \leq j \leq n$ so that the array increases from $1$ to $i$, decreases from $i$ to $j$, and increases from $j$ to $n$.
Input: a zigzag array. Output: the position of $i$ and $j$.
- Upper bound: just going on the array and finding $i$ and $j$, which takes $O(N)$.
- Lower bound: I think that we need to find pairs $i$ and $j$ for which $k$ is bigger than $i$ in $n$ elements, I don't know how to solve it.