Ничего сложного тут нет, все в рамках доступной старшекласснику математики. Откройте книгу Кормена и почитайте первые главы, там это объяснено так, что запомнится на всю жизнь.
Простите, но человек, который претендует на должность software engineer, должен уметь оценивать сложность алгоритмов или хотя бы помнить сложность распространенных алгоритмов, просто потому, что даже если он никогда не будет писать быструю сортировку, он должен знать границы ее применимости. И он так же должен понимать, что сложность быстрой сортировки в худшем случае совсем не O(NlogN), как некоторые кандидаты считают :-)
В США есть нетфликс и хулу, позволяющие смотреть фильмы и сериалы на вполне себе законных основаниях. Когда есть удобная, законная система доставки контента, торренты не нужны :)
1) Где здесь показано, что время выполнения алгоритма действительно является полиномиальной функцией от размера задачи?
2) В чем причина «блaгоговейного страха» народа перед заголовком? У нас тут клуб выпускников филфака?
>> уметь быстро и без ошибок писать эти алгоритмы.
вовсе нет. на этих соревнованиях необходимо выжимать все что только можно из компилятора, стандартной библиотеки и языка как такового в целом. Попытка «написать быстро и без ошибок qsort» равносильна провалу, потому что пока вы ее будете писать другие команды уже решат задачу.
1) Где здесь показано, что время выполнения алгоритма действительно является полиномиальной функцией от размера задачи?
2) В чем причина «блaгоговейного страха» народа перед заголовком? У нас тут клуб выпускников филфака?
вовсе нет. на этих соревнованиях необходимо выжимать все что только можно из компилятора, стандартной библиотеки и языка как такового в целом. Попытка «написать быстро и без ошибок qsort» равносильна провалу, потому что пока вы ее будете писать другие команды уже решат задачу.