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: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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: invalid
Status: newclosed

Sorry, these time complexities are not at all inconsistent.

comment:2 Changed 8 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:3 Changed 8 years ago by simonmar

Operating System: UnknownUnknown/Multiple
Note: See TracTickets for help on using tickets.