Opened 10 years ago

Closed 10 years ago

Last modified 8 years ago

#969 closed bug (invalid)

Inconsistent complexities in Data.Set

Reported by: dpt@… Owned by:
Priority: normal Milestone:
Component: libraries/base Version: 6.6
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


The documentation for Data.Set says that 'insert' can be performed in time O(log n). On the other hand, the same operation can also be done with 'singleton' followed by 'union', for a claimed complexity of O(n), which doesn't seem credible.

Change History (3)

comment:1 Changed 10 years ago by dpt@…

  • Resolution set to invalid
  • Status changed from new to closed

Sorry, these time complexities are not at all inconsistent.

comment:2 Changed 8 years ago by simonmar

  • Architecture changed from Unknown to Unknown/Multiple

comment:3 Changed 8 years ago by simonmar

  • Operating System changed from Unknown to Unknown/Multiple
Note: See TracTickets for help on using tickets.