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 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.
|
|
|
|
