<p>Any algorithm would need $\Omega(\log n)$ queries.</p>

<p>To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$.</p>

<p>Notice that in these notations we are looking to bound $f(\lfloor n/2 \rfloor)$.</p>

<p>Claim: $f(k)\ge \log k$.</p>

<p>Proof:</p>

<p>Consider the first query made by the algorithm.</p>

<p>If it was done within radius $k/2$ of the interval (i.e. somewhere in $[m-k/2,\ldots,M+k/2]$), and found the median at the spot, then we still need at least $f(k/2)$ queries to decide the problem.</p>

<p>If it was done outside that radius, consider the case where the queried cell did not contain the median. Once again, this leaves us with at least $f(k/2)$ queries to be made.</p>

<p>Continue with induction and you get the $\Omega(\log n)$ bound.</p>

CC BY-SA 3.0
2015-04-07T14:21:32.787Z
2015-04-07T14:31:53.000Z
2015-04-07T14:31:53.000Z
R B
<p>This is inspired by [1] (which still needs answers).</p>

<blockquote>
  <p>What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a <strong>sorted</strong> integer array of size $n$, how to determine whether there exists some element which occurs more than $\lfloor n/k \rfloor$ times?</p>
</blockquote>

<hr>

<p><strong>Note 1:</strong> The original problem [1] focuses on $k=2$, i.e., the "majority detection" problem. There is a simple $\Theta(\log n)$ algorithm for it: Only the median, called $m$, can be the majority. We can learn the length of the $m$ contiguous block using binary search.</p>

<blockquote>
  <p>However, is $\Omega(\log n)$ a lower bound for $k = 2$?</p>
</blockquote>

<p><strong>Note 2:</strong> For <em>unsorted</em> array, [2] gives an optimal $O(n \log k)$ algorithm. The lower bound is proved using the decision-tree technique (section 5). I failed to extend it to the sorted case.</p>

<hr>

<p>[1] <a href="https://cs.stackexchange.com/q/41072/4911">Lower bound of finding majority element in an ordered array. @ cs.exchange</a></p>

<p>[2] <a href="http://dspace.library.cornell.edu/bitstream/1813/6345/1/82-505.pdf" rel="nofollow noreferrer">Finding Repeated Elements</a> by J. Misra and David Gries, TR, 1982.</p>

<ds.algorithms><lower-bounds><decision-trees>
Lower bound for finding repeated elements in sorted array
hengxin
# Lower bound for finding repeated elements in sorted array

(Asked by: username_0 on 2015-04-07)

This is inspired by [1] (which still needs answers).

> What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a **sorted** integer array of size $n$, how to determine whether there exists some element which occurs more than $\lfloor n/k \rfloor$ times?

---

**Note 1:** The original problem [1] focuses on $k=2$, i.e., the "majority detection" problem. There is a simple $\Theta(\log n)$ algorithm for it: Only the median, called $m$, can be the majority. We can learn the length of the $m$ contiguous block using binary search.

> However, is $\Omega(\log n)$ a lower bound for $k = 2$?

**Note 2:** For *unsorted* array, [2] gives an optimal $O(n \log k)$ algorithm. The lower bound is proved using the decision-tree technique (section 5). I failed to extend it to the sorted case.

---

[1] [Lower bound of finding majority element in an ordered array. @ cs.exchange](https://cs.stackexchange.com/q/41072/4911)

[2] [Finding Repeated Elements](http://dspace.library.cornell.edu/bitstream/1813/6345/1/82-505.pdf) by J. Misra and David Gries, TR, 1982.

**Tags:** ds.algorithms, lower-bounds, decision-trees

---

## 1 answers

### Answer by username_1 on 2015-04-07. Score: 2 | Accepted answer

Any algorithm would need $\Omega(\log n)$ queries.

To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$.

Notice that in these notations we are looking to bound $f(\lfloor n/2 \rfloor)$.

Claim: $f(k)\ge \log k$.

Proof:

Consider the first query made by the algorithm.

If it was done within radius $k/2$ of the interval (i.e. somewhere in $[m-k/2,\ldots,M+k/2]$), and found the median at the spot, then we still need at least $f(k/2)$ queries to decide the problem.

If it was done outside that radius, consider the case where the queried cell did not contain the median. Once again, this leaves us with at least $f(k/2)$ queries to be made.

Continue with induction and you get the $\Omega(\log n)$ bound.


---

