Какова сложность поиска элементов в структурах данных set и unordered_set?

В std::set сложность поиска в среднем $O(\log n)$, так как он основан на сбалансированных двоичных деревьях поиска (обычно красно-черных де