Здравствуйте, ylp, Вы писали:

ylp>Я где-то говорил, что они возможны?


Как я уже писал, если рассуждать об алгоритмах, которые невозможны практически для общего случая, то твой ответ неверен, а правильный ответ — константное время.

ylp>Я привел в пример алгоритм сортировки, работающий быстрее чем O(N). * **
_{* subject to terms and conditions
** not really}


ylp>Теперь напрягитесь и подумайте, что значит "commonly" и что в случае с сортирующими сетями такое "elementary operation that takes a fixed amount of time to perform". Подсказка — в сортирующих сетях за один интервал времени работают параллельно несколько узлов, а не один.

Выделил ключевое слово.