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