Почему время выполнения алгоритма выбора равно O (n)?

Согласно Википедии , алгоритм выбора имеет время выполнения O (n) , но меня это не убеждает. Может ли кто-нибудь объяснить, почему это O (n) ?

При обычной быстрой сортировке время выполнения составляет O (n log n) . Каждый раз, когда мы разделяем ветвь на две ветви (большую, чем стержень, и меньшую, чем стержень), нам нужно продолжить обработку обеих сторон ветвей, тогда как Алгоритму выбора требуется обработать только одну сторона ответвления. Я полностью понимаю эти моменты. Но если вы думаете об алгоритме двоичного поиска, после того, как мы выбрали средний элемент, мы также продолжаем поиск на одной стороне ветви. Так делает ли это алгоритм O (1) ? Нет , конечно, алгоритм двоичного поиска по-прежнему O (log N) вместо O (1) . Это то же самое, что и элемент поиска в двоичном дереве поиска. Мы ищем только одну сторону, но мы по-прежнему рассматриваем O (log n) вместо O (1) .

Может кто-нибудь объяснить, почему в алгоритме выбора, если мы продолжим поиск одной стороны, можно будет рассматривать O (1) вместо O (log n) ? На мой взгляд, алгоритм таков: O (n log n) , O (N) для разделения и O (log n) для количества раз, чтобы продолжить поиск.