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$

1 Answer 1

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$
2
  • $\begingroup$ tnx. but i cant f=understand why log ((n+1)(n)/2) is omega(logn) $\endgroup$
    – aradona
    Jul 25, 2017 at 21:44
  • $\begingroup$ That's a nice exercise for you. $\endgroup$ Jul 25, 2017 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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