#4086: Data.List 'nub' function is O(n^2) ---------------------------------+------------------------------------------ Reporter: Pete | Owner: Type: bug | Status: new Priority: normal | Milestone: 6.14.1 Component: libraries/base | Version: 6.12.1 Keywords: | Difficulty: Easy (less than 1 hour) Os: Unknown/Multiple | Testcase: Architecture: Unknown/Multiple | Failure: Documentation bug ---------------------------------+------------------------------------------ Changes (by simonmar):
* difficulty: => Easy (less than 1 hour) * milestone: => 6.14.1 * os: Linux => Unknown/Multiple * architecture: x86 => Unknown/Multiple * failure: Runtime performance bug => Documentation bug Comment: Given nub's type, the best complexity it can have is O(n^2). See #2717 for a proposal (currently abandoned) to add a different `nub` with O(n log n) complexity to `Data.Set`. You're quite right that the docs should be improved here, so I'll leave the ticket open. If you want to consider adopting #2717, that would be a worthwhile step I think. -- Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4086#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler _______________________________________________ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs