The Math Forum

Search All of the Math Forum:

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

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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,972
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 <> writes:

> On 7/25/2012 4:06 PM, Ben Bacarisse wrote:
>> Patricia Shanahan <> 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.


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

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.