Why is SortedDictionary<K, V>.GetEnumerator O(log n) but SortedSet<T>.GetEnumerator O(1)?
.net, asymptotic-complexity, big-o, sorteddictionary, sortedset
Solution
I completely agree with you.
The `SortedSet` uses the red black tree structure internally which is guaranteed to be balanced (Wikipedia; Red-Black Trees, R. Sedgewick, Princeton University). Therefore the height is limited by `2 * log2(n + 1)`. Even a code comment in SortedSet.cs points that out and the size of the enumerator's stack is set accordingly.
The `while` loop that prepares the stack is O(log n) in both initializing and proceeding (`MoveNext`) the enumerator.
Feedback on the MSDN documentation referring to this discussion submitted.
Update:
By today Microsoft finally updated the documentation. For the 4.0 version it still states it's an O(1) operation. Although I doubt it, I can leave it at that.
Problem
From the `SortedSet<T>.GetEnumerator` documentation: This method is an O(1) operation From the `SortedDictionary<K, V>.GetEnumerator` documentation: This method is an O(log n) operation, where n is count. Can both the statements be true, considering `SortedDictionary<K, V>` is internally implemented as a `SortedSet<KeyValuePair<K, V>`? I checked the `GetEnumerator` code of `SortedDictionary` class - it directly uses the `SortedSet`'s enumerator. I noticed `SortedSet`'s enumerator implementation and it seemed to me it does have O(log n) characteristic (here is the code): ``` public SortedSet<T>.Enumerator GetEnumerator() { return new SortedSet<T>.Enumerator(this); } //which calls this constructor: internal Enumerator(SortedSet<T> set) { this.tree = set; this.tree.VersionCheck(); this.version = this.tree.version; this.stack = new Stack<SortedSet<T>.Node>(2 * SortedSet<T>.log2(set.Count + 1)); this.current = (SortedSet<T>.Node) null; this.reverse = false; this.siInfo = (SerializationInfo) null; this.Intialize(); } private void Intialize() { this.current = (SortedSet<T>.Node) null; SortedSet<T>.Node node1 = this.tree.root; while (node1 != null) { SortedSet<T>.Node node2 = this.reverse ? node1.Right : node1.Left; SortedSet<T>.Node node3 = this.reverse ? node1.Left : node1.Right; if (this.tree.IsWithinRange(node1.Item)) { this.stack.Push(node1); node1 = node2; } else node1 = node2 == null || !this.tree.IsWithinRange(node2.Item) ? node3 : node2; } } ``` Doesn't that mean the documentation is wrong and `SortedSet<T>.GetEnumerator` is O(log n)? Nothing much about performance of `GetEnumerator` call, just ensuring if I understand correctly.