Re: random numbers' function

James Dow Allen <jdallen2000@xxxxxxxxx> writes:

On Jan 22, 10:49 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
p...@xxxxxxxxxxxxxxxxx (Pascal J. Bourguignon) writes:
James Dow Allen <jdallen2...@xxxxxxxxx> writes:
On Jan 22, 3:18 am, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:
Tagore said:
And therefore not guaranteed to terminate, at least with a perfect
random generator.

Not wishing to cause trouble, but all solutions posted have this
defect, to which I offer no perfect remedy.  Worst case time
for the (non!-)algorithm is therefore O(oo).

Not exactly. ... the algorithm will terminate with a
probability of 1.

Yes, the algorithm terminates with probability 1 but Big-O is not
defined that way.  There is no function that can be shown to bound the
number of iterations by any constant multiple which is presumably what
James means by O(oo).  Algorithms like this are in a no-mans-land
where plain Big O does not really make sense.

I am, in essence, agreeing with you on this one since the only
realistic solution is to abandon the plain definition of Big O and
use asymptotic probabilistic analysis (as you outline).

And I'll accept this! (We're all so agreeble today --- must be the
refreshing change in Free World Leaders! :-) Worst-case behavior
may still be important -- the danger isn't that the Sun will
extinguish
before the random number is generated, but deadline miss if the
need arises in a real-time process.

I don't remember which regular posters castigate qsort for its
worst-case behavior, but qsort defenders may wish to cite the
above admission by respected Mr. Bacarisse in future.

I'd hate to spoil the atmosphere, but do I detect a hint of sarcasm?
I can't imagine why anyone would consider me respected here.

Anyway, the other reason for my suspicion is that I don't see the
connection with qsort (either the C function or the algorithm) so I am
a bit baffled about what I may have "admitted"! Most sort algorithms
yield to analysis quite readily and don't involve any random numbers
(and almost never real ones). If you do an average case analysis, all
that is needed (apart from a huge initial assumption) is some
combinatorics. The answers you get will be as reliable as the
assumption you make about the distribution of inputs.

<snip>
--
Ben.
.

Quantcast