0
$\begingroup$

I am currently studying for a test on data structures.

I have to find the lower and upper bounds for the following problem:

An array is called a zigzag array if there are $1 \leq i \leq j \leq n$ so that the array increases from $1$ to $i$, decreases from $i$ to $j$, and increases from $j$ to $n$.

Input: a zigzag array. Output: the position of $i$ and $j$.

My answer:

  • Upper bound: just going on the array and finding $i$ and $j$, which takes $O(N)$.
  • Lower bound: I think that we need to find pairs $i$ and $j$ for which $k$ is bigger than $i$ in $n$ elements, I don't know how to solve it.
$\endgroup$
0
$\begingroup$

The obvious lower bound is $\Omega(\log n)$, since there are $\binom{n+1}{2}$ possible answers. It is likely that using smart binary search you can find $i,j$ in $O(\log n)$ queries. I suggest starting with the easier case in which $j = n$, that is, the array increases and then decreases, and you want to find its maximum in $O(\log n)$ queries. Such arrays are known as bitonic, and indeed you can find $i$ in $O(\log n)$ comparisons (see for example this solution).

$\endgroup$
  • $\begingroup$ tnx. but i cant f=understand why log ((n+1)(n)/2) is omega(logn) $\endgroup$ – aradona Jul 25 '17 at 21:44
  • $\begingroup$ That's a nice exercise for you. $\endgroup$ – Yuval Filmus Jul 25 '17 at 21:44

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.