> > ... And actually splitting deterministically at 1 (or n) we would > > somehow be out of a "divide and conquer" scenario > > (as indicated above by John), as in effect, as Patricia noted, we are > > examining the elements one by one. > > It's not "splitting deterministically at 1 or n" is splitting that > happens, by outrageous fortune, at 1 or n all n-1 times. If that can > happen, it forms the worst case for random splitting.
I agree with that. I have a problem with the probability being 0, in the asymptotic analysis.
> > > So i think this can be legitimately ruled out, as a real "degenerate" > > case. No? This for the deterministic split. > > Now I can answer your split at 2 or n-1 question. That also gives O(n) > search so you'd have to rule that case out as well. In fact, splitting > at k and n-k for any constant k (with some other rule when n <= k) gives > O(n) search so they all have to be ruled out. too!
Here i am getting lost. Assume that M is the middle index in an arbitrarily large array. Are you saying that if i split, for instance, deterministically at M-1 i suddenly get a O(n) search instead of O(log n) ?
> But to answer... Yes, anything with probability zero > is not considered because it can't happen.
I thought so.
> > The asymptotic bound is not what happens when n gets very large...
well it seems to me that there is a limit in the definition.
So, to recap, what would be the answer? That only a deterministic search using exactly the middle point is O(logn), while any other deterministic and the random-split search is O(n) ?