Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

Topic: binary search with arbitrary or random split
Replies: 1   Last Post: Jul 25, 2012 8:00 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View  
Ben Bacarisse

Posts: 1,087
Registered: 7/4/07
Re: binary search with arbitrary or random split
Posted: Jul 25, 2012 8:00 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.