3
$\begingroup$

Given a bit sequence of length a, what is the minimum number of comparisons needed to determine if it contains a pair of consecutive 1's in BigO notation

$\endgroup$
2
$\begingroup$

Without any further information about the sequence, the complexity is $\mathcal{O}(n)$: You have to look at least at every third bit (this is a loose lower bound, obviously, you cannot jump over more than 1 without the possibility of missing a "11". However, there is a $\mathcal{O}(n)$ algorithm:

for(i=0; i<a; i++)
    if(a(i)==1 && a(i+1)==1)return true
return false

Therefore, the best possible asymptotical behaviour is between $\Omega(\frac{1}{2}n)=\Omega(n)$ and $\mathcal{O}(2n)=\mathcal{O}(n)$, e.g. it is $\Theta(n)$.

$\endgroup$
  • 1
    $\begingroup$ Yes, but you can't jump over more than one without the possibility of missing a "11". $\endgroup$ – mrf Feb 9 '13 at 21:03
  • 1
    $\begingroup$ Yes: the difference it makes is that $\frac13n$ is misleading. But true enough, it is entirely up to you to decide if you want to help the reader to understand what it is that you are saying, or not. $\endgroup$ – Did Feb 9 '13 at 21:07
  • 2
    $\begingroup$ Here is another lower bound: 42 (valid for every large enough $n$). "Therefore, my argument is correct." $\endgroup$ – Did Feb 9 '13 at 21:18
  • 1
    $\begingroup$ @CBenni: Why not just change it to "every second bit" and "jump over more than 1" such that your agument will actually make intuitive sense instead of depend on a pointless arbitrarily weakening which there's no reason to make (no matter that you're formally allowed do do it)? $\endgroup$ – Henning Makholm Feb 9 '13 at 21:24
  • 1
    $\begingroup$ @CBenni: $\Omega$ is indeed more correct, but that is not the main problem Did and mrf and I pointed out. Your edit still leaves the strange pointless choice of "every third bit"/"jump over more than 2" in there instead of the intuitively reasonable "every second bit" and "jump over more than 1". $\endgroup$ – Henning Makholm Feb 9 '13 at 21:33

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.