Для алгоритмов, уже описанных в этом топике, оценка среднего случая не так важна, тк в каждом из них она ближе к худшему случаю.
А о сортировках из вашего примера (быстрой и слиянием) автор еще не упоминал, и я уверен, что когда он это сделает, то мы увидим оценку их временной сложности в среднем случае