Decision tree complexity of deciding whether array is "zigzag"
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&lt;t$, the answer is always $A[s]&lt;A[t]$ unless $s=n-1$ and $t=n$, in which case the answer is $A[n-1]&gt;A[n]$.

It is always consistent that the array is zigzag, with $i=n-1$ and $j=n$ (the order is $A[1] &lt; A[2] &lt; \cdots &lt; A[n-2] &lt; A[n] &lt; 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&lt;t \leq n-2$ which weren't compared. It is therefore consistent that $A[s] &gt; A[t]$ whereas $A[t] &lt; A[n-1] &gt; A[n]$ (for example, the order could be $A[1] &lt; \cdots &lt; A[s-1] &lt; A[t] &lt; A[s] &lt; \cdots &lt; A[n-2] &lt; A[n] &lt; 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.