Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

Topic: binary search with arbitrary or random split
Replies: 6   Last Post: Jul 24, 2012 11:14 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
pamela fluente

Posts: 232
Registered: 1/21/06
Re: binary search with arbitrary or random split
Posted: Jul 24, 2012 7:39 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 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) ?



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.