Почему асимптотическая сложность поиска в бинарном дереве поиска составляет O(nlogn)?

Возможно, имелась в виду линейно-логарифмическая сложность, которая обозначается как O(n log n). 1 Она возникает, когда в алгоритме комбинируется перебор всех элементов и уменьшение их количества на каждой итерации. 1

Бинарный поиск, который является примером алгоритма с оценкой временной сложности O(log n), работает по другому принципу: на каждом шаге половина данных отсекается, и поиск продолжается в оставшейся половине. 2 Это означает, что при увеличении размера входных данных вдвое, бинарный поиск требует всего одного дополнительного шага. 2

Таким образом, сложность O(n log n) возникает из-за сочетания перебора всех элементов и уменьшения их количества на каждой итерации, что характерно для алгоритмов с линейно-логарифмической сложностью. 1