Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM 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 redefine 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=OGFz9gt0Fc
 Ben.



