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 25, 2012 6:40 PM


Life intervened, and I had to postpone posting this after I'd already spent some time one it. I see now that there are more messages so the debate may have moved on, but I don't want to lose the time invested so I post this with apologies if its content duplicates other people's contributions.
pam <pamelafluente@libero.it> writes:
> On Jul 25, 4:08 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote: > >> >> No, you can't be any doubt about what my answer is. I said it's linear >> and not logarithmic  O(n) and not O(log(n))  and I've said it more >> than once. I don't think you have any trouble understand that this is >> my answer. >> >> You might have trouble understanding why this is my answer. Here I can >> only say that I've been as clear as I can be. If you could say what >> parts are not clear to you, I could say more. > > Well here the question is another. > > When you answered O(n) you were considering a setting > where the split point does not depend on n.
I didn't make any general remark like that. I make a very specific one: "the key distinction is between reducing the range by a *factor of n* or by a *fixed amount* independent of n" (emphasis added). It's about only two cases, and it's about the reduction in the range, not the formula for the split point.
> Now we have "refined" the formulation making clear the dependence > ("divide and conquer").
You once proposed splitting at n/uniform(1, n) but that does not always reduce the range by anything more than a constant.
> So, now the question is (and it has always been in essence): > > Should one singularity which causes the least upper bound to raise > from O(logn) > to "no better than O(n)" be considered in the computational complexity > assessment, > considered that its probability tends to 0 ? > > Patricia was saying yes.
And I agree. If you don't follow what I say below in clarification, just ignore it and assume that I'm a terrible communicator. You haven't been objecting to Patricia's argument so I presume you accept it. She's right, and if I seem to be saying anything else, it's my bad writing skills.
> You were saying, at one point, that stuff with probability 0 should > not be considered in the asymptotic analysis.
Every case that can occur must be considered in a worstcase analysis. There is no n so large that the probability of a sequence of bad splits is zero. These cases must be included.
> So, in this sense, i was saying that you have not answered to the > corrected formulation of the problem.
I hope I have now. The cost for all nsized cases can be calculated and the worst ones, taking linear time, all have nonzero probabilities.
If you disagree, what is the worstcase cost function? I don't mean what is it asymptotically similar to (i.e. I don't want the big O "summary", I want the actual cost in comparisons of a search of n elements).
> Now, as Patricia recalled, we say that the complexity C(n) is O(logn) > if: > > > limit for n to infinity of C(n) / logn is less than some > constant, say K. >
But you've forgotten something else she said (twice). You don't find a O(f(x)) formula for C(n) until you have found C(n). The big O stuff is throwing you right off  it a way of simplifying your result, not the result itself. Forget it for the moment: what is C(n) for your algorithm? Do you agree that it's just n?
> Now in a probabilistic setting, limits are taken "in probability": > What we are interested in > is to see if: > > > Prob [ limit for n to infinity of C(n) / logn is less than > K ] = 1 > > (this is an "almost sure" convergence (a.s.), as opposed to the "sure" > convergence > used in nonprobabilistic setting)
Well, that's just not how complexity is defined. You can't use big O to mean something new without alerting everyone to this fact.
As for the probabilistic convergence, I have to leave that to you. The formula you have inside Prob[...] does not look like the kind of thing I've see before in such contexts, but since I won't be able to help, it hardly matters that I don't understand your formula.
> or if, at least, the above probability is converging to 1 (a.a.s., > asymptotically almost sure). > > In our case, from what i gathered so far we have a generally O(logn) > problem which only on singularities > might blow up to O(n).
The *problem* is O(log(n)) because there is an O(log(n)) worstcase solution. Your *algorithm* (random slitting) is O(n) in the worst case. I have no idea if these worst cases can be described as singularities but I think (talking off the top of my head) you believe that cost is greater than k*log(n) only on a set of cases with measure zero, and that you can formalise this with one or other of the standard forms of probabilistic convergence. Obviously I can't say if this it true or not.
> So when we consider C(n) above we can split it into 2 parts: one of > order O(logn) and another ("atomic") > of order O(n). But the second part, as n goes to infinity has a > probability going (very quickly) to 0.
I don't think it's that simple. You can't describe cases as being O(log(n)) or O(n). If you run your algorithm with n=42 and it takes 36 compares, is that an O(log(n)) or an O(n) case? The probabilistic analysis must take the distribution of splits (and inputs if need be) into account to give a random variable in place of the cost function. You may then be able to determine that this variable has a limit as n>oo using one of the limit definitions ("almost surely" is only one).
Alternatively, you might be able to derive the expectation etc. of this variable to give yet another measure of the algorithm's performance.
This is not something I know much about, but it does seem clear that you can't partition the cases into two. Every set of split points determines a cost and has a distinct probability of occurring. They must all be considered.
> So we have that the above limit holds with probability 1.
That needs to be established. It does not seem unlikely but probabilities are notoriously counterintuitive.
> In probabilistic contexts i have always seen considering forms of > convergence a.s. or a.a.s., or anyway involving > probability.
Right, but in case it has not yet been said enough, in complexity theory, you don't have to take any limits. If the worstcase cost function is n, you can call it O(n) without using a limit argument and without using any probability theory. Whatever measure you end up deciding to use, you can't call it worstcase complexity.
> Also, from an intuitive point of view, it would be ridiculous, imho, > to consider the problem O(n). Just think: > imagine n is as big as an RSA modulus. The probability of the > "singularity" causing O(n) > is a number inconceivably small, that no computer on earth could even > ever represent.
I can't stop you thinking it ridiculous, but complexity classes are defined a particular way and you can't alter that on your own. You can choose to use what you consider a more intuitive measure, but an O(n) algorithm will remain and O(n) algorithm.
> This was in essence my argument. Clearly, i dont expect to be right, > and actually i would like to be corrected. >
 Ben.



