I am currently studying for a test on data structures.
I have to find the lower and upper bounds for the following problem:
Input: an array with $n$ numbers.
Output: boolean answer for the question if there exist $1\le i\le j\le n$ so that:
- All the elements in the array between $1$ and $i$ are in ascending order.
- All the elements in the array between $i$ and $j$ are in descending order.
- All the elements in the array between $j$ and $n$ are in ascending order. We call this type of array a zigzag array.
I have these ideas: in general, in order to find an upper bound I am looking for an efficient algorithm. For lower bound I am using the decision tree model. For example: in order to find the lower bound for comparison sort algorithms of $n$ numbers, we have $n!$ leaves on the binary decision tree, so we have $n!$ different possibilities for sorting $n$ numbers, which results in an $Ω(n \log n)$ lower bound.
For upper bound I am thinking about just moving from the first element step by step and finding if the array is a zigzag or not, so upper bound is $O(n)$
Lower bond: I don't know how many different possibilities of zigzag arrays of length $n$ we have, so i don't know how so solve it. If one of you has a different method of finding the lower bound I will be happy to know.