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 7:29 PM
|
|
pam <pamelafluente@libero.it> writes:
> On Jul 26, 6:56 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>
> > Discussed above. You agree that the cost function in n. n is in
> O(n)
>> and not in O(log(n)) these are theorems of mathematics. In those cases
>> where O() is defined using limits, these are not probabilistic limits,
>> they are normal analytic limits.
>
>
> Thank you Ben.
>
> I think we agree in all. Even about what we can "safely
> disagree" ;-)
>
> [btw, i normally use ;-) as a form of smile because is just under my
> finger, so don't see in it any malice
> but just a smile ;-) ]
As I said before, take care. It takes longer to explain your particular
usage than to use the normal one, so you'll probably use it
unannounced. People will read it for what it is, not for what you
intend.[1]
I'd always prefer the cost of the extra key stroke over the possibility
of being misunderstood.
> About the "why i care", is simply because i am curious. Instead of
> being curious about the latest gossips
> i sometimes get curious about these questions ;-)
>
> I can see that you have come to see O() no more in its "original"
> meaning, but almost as something
> else, a symbol denoting a "class".
>
> Well i can understand that, I don't have a CS background, so to me
> that does not sound quite familiar.
> When i see O() i understand it uniquely in the sense involving a
> limit: i don't see any "class".
Writing f = O(g) establishes a relation between f and g, and it turns
out that this slightly odd looking = (there is no literal equality
there) has the properties of an equivalence relation. It therefore
partitions the set of functions into equivalence classes. I used class
as a shorthand, because equivalence class is such a mouthful.
There's no change in meaning, as I'm sure you know.
> A little search reveals also this interesting article:
>
> http://en.wikipedia.org/wiki/Big_O_in_probability_notation
>
> And if we are in a probabilistic setting, i am still of the opinion,
> we need to use the probabilistic definition.
> Not the definition suitable for deterministic contexts.
Does this need extend input distributions? There are polynomial SAT
solvers that work for "most" inputs, but we still say that SAT is not
(apparently) in P. Some quicksorts are only O(n^2) for vanishingly
rare inputs. Would you use a probabilistic definition of asymptotic
equivalence for these sorts of probability?
I think these examples make it clear why you need a new notation. You
can't re-define O(f) with a probabilistic meaning without there being
way too much scope for confusion.
<snip>
[1] I always think of this sketch when this sort of thing comes up:
http://www.youtube.com/watch?v=OGFz9gt0-Fc
--
Ben.
|
|
|
|
