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:02 PM


pam <pamelafluente@libero.it> writes:
> On Jul 27, 1:29 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote: <snip> >> 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. > > Alas, it looks like it has already invented since long time. So i > arrived late :(
Except that the paper you cite does not seem to use the same definition that you were proposing. Of course, if you like this definition, go ahead and you their notation  no need to proliferate symbols  but you'll need a way to write it for Usenet posts as your quote below shows so clearly.
> Making a quick check, it looks like that (while someone here was > accusing me of "gibberish" :)
It's possible that what you wrote was gibberish (I'm sorry but I don't recall). What's clear is that the paper you cite does not use the same reasoning you do. It uses what looks like a significantly different definition. In particular it does not rely on "almost sure" convergence. It's possible, of course, that their definition is that same as yours. It would make an interesting exercise to see if that is the case.
> using the big O in the probabilistic sense is the norm even in > official CS literature (SIAM) when > dealing with probabilistic formulations.
That's not a clear way to report it. The paper you cite uses big O as everyone else does. They define another relation (with it's own notation) that relies on probabilities. I'd need a few more references to know if either this new notation or the specific definition they use is anything like "the norm".
What is still not in doubt is that big O is used, even in the context probabilistic algorithms, to mean what it has always meant. The textbook I cited earlier does so, and so does the paper you've referenced here. (I'm sorry to keep banging on about this but you've worded the above remark in such a way that I felt it needed to be said again.)
> See for instance: > > http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.2557 > http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=DCD58376005D28855D7D062968CC925F?doi=10.1.1.30.2557&rep=rep1&type=pdf > > You can read at pag 4, under 1.3 just the same things i have been > saying here ;)
Well, not "just the same"; "similar" is the best I can do right now. They don't use almost sure convergence and it's not clear how their definition relates to your algorithm. Have you been able to show that your uniform splitting search is OPr(log(n))? (I'm using my suggested OPr because the notation they use does not obviously translate to ASCII.)
> "Just like bigO function serves to represent the complexity bounds of > deterministic algorithms, we employ O to represent complexity bounds > of randomized algorithms. We say a randomized algorithm has resource > (like time, space, etc.) bound O(g(n)) if there is a constant c such > that the amount of resource used by the algorithm (on any input of > size n) is no more than c g(n) with probability 1 1=n for any > 1 > ... "
That went wrong. For everyone else (is anyone else reading this?) the paper uses O with a tilde over it for this probabilistic bound, and the definition is that
We say a randomized algorithm has resource [...] bound O(g(n)) if there is a constant c such that the amount of resource used by the algorithm (on any input of size n) is no more than c a g(n) with probability >= 1  1/(n^a) for any a > 1.
> (i found similar stuff in several other papers) Hmm, it's time i > begin to read some CS article too ... :)
Do they all use this definition? Any agreement between them on the notation to be used?
 Ben.



