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.
Decision tree complexity of deciding whether array is zigzag
data structures;decision tree