Search All of the Math Forum:

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

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

 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

On Jul 24, 1:05 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> pam <pamelaflue...@libero.it> 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

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

Date Subject Author
7/24/12 pamela fluente
7/24/12 Joshua Cranmer
7/24/12 pamela fluente
7/24/12 pamela fluente
7/24/12 Joshua Cranmer