1
$\begingroup$

Suppose you are given an array of $n$ integers with duplicates in non-decreasing order. The goal is to find the locations where a value is different from its neighbor. For example, given the array $arr={3,3,5,5,5,200,200,200,200,209}$, the output would be: ${2,5,9}$. Obviously, this can be done in linear time. I am trying to improve upon this using a binary search. Let $k$ be the number of output locations. In $O(k \log n)$ time we can get our answer. To find first location, check locations $2,4,8,$etc. Suppose you find that $arr[1]<arr[2^{j}$], recursively search the interval from $2^{j-1}$ to $2^j$-1.

My QUESTION: In the worst case, $k=O(n)$. I do NOT want to ever pay $O(n \log n)$ since the naive algorithm is $O(n)$. However, I do not pay $O(n \log n)$ for $k=O(n)$ since the binary searches terminate in $O(1)$ time. How do I prove that the algorithm is worst case $O(k \log n)$ when $k << n$ and never worse than $O(n)$?

$\endgroup$

4 Answers 4

2
$\begingroup$

Here is a fairly simple fix. Anytime you "overshoot" in your search (I.e. $A[i]=A[i+2^j]$ but $A[i] \neq A[i+2^{j+1}]$ when you backtrack to find the correct index, also keep track of elements in that range that satisfy the inequality (may as well if your scanning over them anyway). You can pick back up at $A[i+2^{j+1}]$. This way, your running time is $O(n)$ worst case.

$\endgroup$
1
  • $\begingroup$ I think you are right. I originally wrote the algorithm keeping track, but then I thought it was unnecessary. But it does make the argument of O(n) easier. $\endgroup$
    – user118462
    Aug 24, 2017 at 2:59
1
$\begingroup$

In fact you need start binary search $k$ times. Assuming, you use divide & conquer techniques (after found one location x_i, start binary search on x_0..x_i-1 and x_i..x_n separately), algorithm will have runtime $O(n)$.

Algorithm would look as follows:

Search(low, high)
    mid = (low + high) / 2;
    if A[mid] == A[mid - 1]
    {
        if (A[low] < A[high])
        {
            Search(low, mid - 1);
            Search(mid, high);
        }
    }
    else 
    {
        print k_i
        if (low < high)
        {
            Search(low, mid - 1);
            Search(mid, high);
        }
    }

You can see we have $p=O(\log n)$ depth of recursion. Each call takes $O(1)$ operations and we have $2^p = O(n)$ calls. Graph of recursive calls would never have more than $O(n)$ vertices since each pair of neighboring elements is compared only once (or not compared at all).

$\endgroup$
2
  • $\begingroup$ This code costs O(n) even if there is 1 location to output. My idea is to spend k log n time, so if there are a constant number of positions, it will only take O(log n). $\endgroup$
    – user118462
    Aug 25, 2017 at 0:26
  • $\begingroup$ No, if there is 1 location, code costs at most twice of binary search. Look at if A[low] < A[high] line. If minimal and maximal elements of subarray are equal, branch halts. Also, as I understand, runtime is $Ck\log(\frac{n}{k+1}+1)$. $\endgroup$
    – rus9384
    Aug 25, 2017 at 0:33
0
$\begingroup$

A crude argument would be that you dereference a pointer in the array a constant number of times (depending on how you code it...), and hence the asymptotic complexity is at most linear in the input array.

If you want to seek a more formal direction to prove this worst case bound, I suggest you to read about amortized analysis and use its' tools.

Amortized Analysis - Wikipedia

$\endgroup$
1
  • $\begingroup$ This is not about dereferencing pointers. Actually, in my paper we are asking O(1) time queries since these numbers are never stored in an array. But the theoretical question is the same as the one asked. How many comparisons are being done in the worst case? I think it needs calculus to somehow balance the O(k log n) with O(n). $\endgroup$
    – user118462
    Aug 23, 2017 at 20:51
0
$\begingroup$

Let's say your algorithm is roughly: Let k = 0. Then repeatedly either find the smallest k' > k such that arr [k] < arr [k'], or prove that none exist. If you find k', output k' - 1, let k = k', and repeat the search.

You need an algorithm that achieves the following: 1. In the worst case, finding k' takes O (log n). 2. The number of steps finding k' is at most O (k' - k).

I think you can't guarantee n comparisons (because to guarantee this, you need to compare arr [k] < arr [k+1] first in case all elements are different, then arr [k] < arr [k+2] in case every second element is different, then arr [k] < arr [k+3] in case every third element is different and so on).

You can achieve this with a guarantee of at most say 1.5n comparisons, if you grow the indices slowly initially.

$\endgroup$
3
  • $\begingroup$ 1. If k = 0, then algorithm should show that min = max and halt. 2. 1.5n comparisons is a way too many. $\endgroup$
    – rus9384
    Aug 24, 2017 at 13:09
  • $\begingroup$ 1. You should have realised that I didn't use k in the way the OP did, it's quite obvious. 2. You want a guarantee "at most cn comparisons", and simultaneously O (k log n), with k as used by the OP. c = 1 is not possible. Explain why c = 1.5 is "way too many". $\endgroup$
    – gnasher729
    Aug 24, 2017 at 21:34
  • $\begingroup$ Algorithm I wrote has at most $n-1$ comparisons, since two compared elements then are sent to different subarrays. $\endgroup$
    – rus9384
    Aug 24, 2017 at 22:02

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.