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 26, 2012 10:09 AM
|
|
pam <pamelafluente@libero.it> writes:
> On Jul 26, 3:06 pm, Martin Brown <|||newspam...@nezumi.demon.co.uk>
> 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.
<snip>
--
Ben.
|
|
|
|
