# Decision tree complexity of deciding whether array is “zigzag”

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.

• The rule is one question per post. Choose one problem and remove all the rest (or ask them separately). – Yuval Filmus Jul 25 '17 at 19:49
• I'm not sure I understand your problem. Isn't a linear search of the array sufficient to solve it? – quicksort Jul 25 '17 at 20:05
• how do i find the lower bound ? – aradona Jul 25 '17 at 20:06

You can prove a lower bound of $n-3$ comparisons, almost matching the trivial upper bound of $n-1$ comparisons (surely the gap can be closed with a bit more work). The proof uses an adversary argument. Whenever the algorithm compares two elements $s<t$, the answer is always $A[s]<A[t]$ unless $s=n-1$ and $t=n$, in which case the answer is $A[n-1]>A[n]$.
It is always consistent that the array is zigzag, with $i=n-1$ and $j=n$ (the order is $A[1] < A[2] < \cdots < A[n-2] < A[n] < A[n-1]$). Now suppose you make less than $n-3$ comparisons. In particular, if you think of your comparisons as edges on the graph on vertices $\{1,\ldots,n-2\}$ (we ignore comparisons to $A[n-1]$ or $A[n]$), then the graph is disconnected. In particular, there are vertices $s<t \leq n-2$ which weren't compared. It is therefore consistent that $A[s] > A[t]$ whereas $A[t] < A[n-1] > A[n]$ (for example, the order could be $A[1] < \cdots < A[s-1] < A[t] < A[s] < \cdots < A[n-2] < A[n] < A[n-1]$), in which case the array isn't zigzag since it has two disjoint decreasing parts. Hence the algorithm doesn't know the answer.