TreeMultimap.create(TreeMultimap) takes O(n log n)

[GoogleCodeExporter]

Inserting into a binary tree in sorted order is the worst case scenario for a 
red-black tree like the one backing TreeMultimap, and that's exactly what 
happens when you call putAll on another TreeMultimap.

Prior art: TreeMap special cases new-from-SortedMap via buildFromSorted.

Original issue reported on code.google.com by jbel...@datastax.com on 13 Nov 2013 at 5:29

[GoogleCodeExporter]

Original comment by lowas...@google.com on 13 Nov 2013 at 5:44

• Added labels: Package-Collect, Type-Performance

[GoogleCodeExporter]

To be clear: is that actually quadratic time?  I understand that it's the worst 
case scenario, but I'm not sure I follow why that would lead to quadratic time 
instead of O(n log n).

Original comment by lowas...@google.com on 13 Nov 2013 at 5:47

[GoogleCodeExporter]

My apologies, O(n log n) is correct.  I'm not sure if there is a way to edit 
the issue title.

Original comment by jbel...@datastax.com on 13 Nov 2013 at 5:56

[GoogleCodeExporter]

Original comment by lowas...@google.com on 13 Nov 2013 at 6:03

• Changed title: TreeMultimap.create(TreeMultimap) takes O(n log n)

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<issue id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:10

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:17

• Changed state: Migrated

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:08

• Added labels: Restrict-AddIssueComment-Commit