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: 1   Last Post: Jul 26, 2012 10:09 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View  
Ben Bacarisse

Posts: 1,972
Registered: 7/4/07
Re: binary search with arbitrary or random split
Posted: Jul 26, 2012 10:09 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

pam <> writes:

> On Jul 26, 3:06 pm, Martin Brown <|||>
> wrote:

>> Analysing the linear fixed split case :
>>   k  :  N-k
>> 1 < k <= N/2

> This has already been promptly corrected several posts ago. Ben made
> an insightful remark about that.
> We are now dealing with a random splitting which is a function of n.
> (This has also an intuitive meaning, as if it did not depend on n, we
> would not be "dividing" anything.)

This issue is not whether splitting "is a function of n" or not. Please
read what I said again -- I repeated it when you made a similar claim
only a few posts ago. Splitting at, say, n-2 is clearly a function of n
but it reduces the search range by a constant at each step.

Also, Martin Brown is not saying something that contradicts what's been
said already. He's just adding detail. There are splitting choices
that give neither linear not logarithmic costs, and his example is only
one of an infinite number of other costs. Trying to categorise them one
by one is hopeless.


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.