Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: binary search with arbitrary or random split
Posted:
Jul 24, 2012 7:39 AM


On Jul 24, 1:05 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote: > pam <pamelaflue...@libero.it> writes: https://groups.google.com/group/comp.theory/browse_thread/thread/f712492127047301/ffb8397007f4abf9#ffb8397007f4abf9
> > ... 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 n1 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 n1 question. That also gives O(n) > search so you'd have to rule that case out as well. In fact, splitting > at k and nk 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 M1 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 randomsplit search is O(n) ?



