Why is SortedDictionary<K, V>.GetEnumerator O(log n) but SortedSet<T>.GetEnumerator O(1)?

Question

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.

Answer 1

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.