Not for all operations, https://msdn.microsoft.com/en-us/library/ms132339(v=vs.110).aspx .

It seems that read operations are and O(1), but modifications can be O(n) . It is probably implemented as list where elements are stored in sorted order not a tree (thus the name SortedList). It means that inserting and removing can cause shifting of all the elements.