# BigO sorting complexity help

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

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)$.

• Yes, but you can't jump over more than one without the possibility of missing a "11". – mrf Feb 9 '13 at 21:03
• 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. – Did Feb 9 '13 at 21:07
• Here is another lower bound: 42 (valid for every large enough $n$). "Therefore, my argument is correct." – Did Feb 9 '13 at 21:18
• @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)? – Henning Makholm Feb 9 '13 at 21:24
• @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". – Henning Makholm Feb 9 '13 at 21:33