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 8:00 PM


Patricia Shanahan <pats@acm.org> writes:
> On 7/25/2012 4:06 PM, Ben Bacarisse wrote: >> Patricia Shanahan <pats@acm.org> writes: >> >>> On 7/25/2012 9:25 AM, pam wrote: >>> ... >>>> 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. >>>> >>>> You were saying, at one point, that stuff with probability 0 should >>>> not be considered in the asymptotic analysis. >>> ... >>> >>> Ben, do you agree with the following? >>> >>> A case can be ignored for calculating worst case complexity if, and only >>> if, there exists a natural number N such that the probability of that >>> case is zero if the input size is greater than N. >>> >>> Not tending to zero, not approximately zero, not zero for some large >>> inputs, but zero for *all* inputs larger than some finite size. >> >> Is sounds right but you seem to be using "case" in an a way that does >> not match my usage. A "case", for me, is one execution of the >> algorithm, and the cost for some size is just the maximum cost of all >> the possible executions with that input size. >> >> You seem to use "case" to means a particular class of executions (maybe >> characterised by some behaviour of the algorithm or some property of the >> inputs) rather than single executions. With that meaning, yes, I agree. >> > > Can you suggest a better term for a related set of executions, such as > those that are equivalent to a linear scan?
No, not off hand, but I don't think it matters. "Case" is a very general word and makes sense being used for either. In fact, your meaning subsumes mine since any execution can be seen as a case with one member. I don't see much scope for confusion  the context will probably make it clear if a case is class of executions or a single one.
Gosh that's wordy. So, yes, I agree.
 Ben.



