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 9:26 PM


pam <pamelafluente@libero.it> writes: <snip> > I am doing this to make the split point explicitly dependent on n > or else we have experts like Ben coming out and saying that it's > O(n) for reason due to the split point being independent of n ;)
What does the wink signify to you? To me it means, "I know this not what Ben said but I hope I get a rise from him by saying it". If that's want you were going for, you nailed it; if not, you may want to rethink you use of smilies.
<snip> > Ben seemed to agree at one point that vanishing events should not be > considered ("vanishing" meaning > with a limiting probability 0), but then said he is in agreement with > Patricia. > > So at the moment i have still not understood what is the answer ;)
That's a flatout lie. I said I did not know what a "vanishing event" was, so how could you read that as agreeing to anything about them at all? I don't think you are confused about what I said, I think you want to misrepresent it for your own purposes.
<snip> > Well in any case i might say that is O(logn) "almost certain". Can we > agree on that ? Or no ?
Why do you care? No one would use a random slit when a binary split is simple and efficient. What's the actual algorithm you have in mind whose worstcase cost you are so keen to be logarithmic? There's more to this that you are letting on, and it's starting to have a hint of obsession about it. Spill the beans.
 Ben.



