1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.