Re: Sort benchmark and a classic paper by Gray

nmm1@xxxxxxxxx wrote:
In article <SOqdnZwo4I2gLIrXnZ2dnUVZ8i6dnZ2d@xxxxxxxxxxxx>,
Terje Mathisen <"terje.mathisen at tmsw.no"> wrote:
They are both expected to run in (N), and will do so as long as the keys are sufficiently random.

And uniformly distributed - that is even more important.

With my engineering (vs pure math) background, I'm taking "sufficiently random" for a binary value to mean a uniform (flat) probability distribution.

If all the bits are indeed random, the resulting distribution is of course uniform.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
.

Relevant Pages

  • Re: Probability in an infinite sample space
    ... It is often assumed that if no distribution is specified, then a uniform ... no such thing as a uniform probability distribution on a countably ... distribution on a countably infinite space, ...
    (sci.math)
  • Re: An uncountable countable set
    ... there are no uniform distributions over countable sample spaces, ... probability distribution. ... probability associated with it: that fraction. ...
    (sci.math)
  • Re: Compression contests
    ... whether the next symbol's probability distribution is affected by the ... your algorithm on so called "memoryless sources" with an "uniform ... The terms "memoryless source" should be just as alarming as "uniform ... can't predict the sequence no matter what algorithm you use. ...
    (comp.compression)
  • Re: Confirmation of Shannons Mistake about Perfect Secrecy of One-time-pad
    ... of M from the known joint probability distribution ... probability distribution of M and C when C is fixed) ... the assumption that K is uniform when C is fixed ... is incorrect. ...
    (sci.math)
  • Re: Flat clear suggestion
    ... remainder up. ... I used it on a uniform and found it to be as flat as ... After working with Pactra Acrylics you CANNOT brush with ...
    (rec.models.scale)
Loading