Cum se determină complexitatea temporală a operației de citire a unui element din structura de date SortedDictionary?

În C#, structura de date SortedDictionary este implementată pe baza unui arbore roșu-negru, un arbore binar de căutare echilibrat.

Complexitatea temporală a operației de citire (căutarea unui element după cheie) în SortedDictionary este O(log n), unde n reprezintă numărul de elemente din dicționar.

Acest lucru se datorează faptului că căutarea parcurge arborele, reducând numărul de verificări în timp logaritmic, spre deosebire de, de exemplu, Dictionary, unde căutarea are o medie de O(1), dar fără ordonarea cheilor.