The Math Forum

Search All of the Math Forum:

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

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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 <> wrote:
> pam <> writes:

> > ... 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
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]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.