Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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 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) ?
|
|
|
|
