Summary: Erroneous documentation and lacking randomization for
           Product: D
           Version: unspecified
          Platform: Other
        OS/Version: Mac OS X
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos

--- Comment #0 from Magnus Lie Hetland <> 2011-02-01 07:57:21 
PST ---
The topN function in std.algorithm is documented as having a running time of
Ο(r.length), if stable. This should be an *expected* (or average-case) running
time of O(r.length), with a worst-case running time of O(r.length^^2), based on
the current implementation, which is the Randomized-Select algorithm.

Also, the implementation should probably use randomization (as in the standard
formulation of the algorithm), rather than consistently picking the middle
element. This will entail a slight overhead in picking the pivot, but this will
(on average) only be done a logarithmic number of times, so the cost should be
negligible. The gain from this is, of course, that consistent worst-case
behavior in the face of certain inputs is avoided.

Configure issuemail:
------- You are receiving this mail because: -------

Reply via email to