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 26, 2012 10:21 AM

Advanced Search

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

Posts: 1,526
Registered: 7/4/07
Re: binary search with arbitrary or random split
Posted: Jul 26, 2012 10:21 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

pam <pamelafluente@libero.it> writes:

> Thank you Ben, for the complete clarification. I think i agree in all.
>
> If the definition does not involve probability, than i have no choices
> and i can only agree with you.


Well, only once case left (uniform splitting) and we are in total
agreement!

You still have not answered the "why do you care" question. It really
does matter. If your interests are practical, a probabilistic measure
of complexity is a good way to go. If your interest is in relating some
work of your own to existing work on complexity theory, you have to
accept the standard meaning of a complexity class.

> (Clearly maintaining a reservation on the "intuitive" aspects, in case
> the
> events leading to O(n) can be proven disjoint and have a probability
> converging to 0.
> Where i think that in a "probabilistic context" they should be dropped
> for a "useful" assessment (see my RSA example).
> So while i can accept the complexity class "definition", i may also
> argue it does not seem to make much sense in the probabilistic case.)


You are free to use some other measure of complexity that you find more
intuitive and useful. I am glad you accept the standard definition.
Can I suggest you choose a notation for your probabilistic measure? I
don't think there is a standard one.

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