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 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 : Nk >> >> 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, n2 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.



