According to Microsoft Doc, the SortedDictionary.GetEnumerator() method is an O(log n) operation in C#. SortedDictionary is backed by SortedSet. Looking at .NET source line 1911 to 1923, when the GetEnumerator() method is called, a new Enumerator is instantiated which creates a Stack<T> internally. Then the Stack<T> is filled in in the Initialize() method. This is an O(n) operation, not O(log n)!
I'd appreciate it if someone explains the reason for O(log n).
the Stack is filled in in the Initialize() method. This is an O(n) operation, not O(log n)!
No, not really. The Stack<T> collection is filled only to the deepest level of the binary tree representing the sorted data. The Initialize() method traverses the binary tree, pushing data nodes onto the stack until it reaches the first node that will be returned by the enumerator.
The binary tree's depth is log n, and the Initialize() method loops just once per level of the tree, so the cost of the loop is also O(log n). Just like the documentation says.
The overall cost of enumerating the collection will be O(n), but simply initializing the enumerator is only O(log n).
