Yes, I saw that error after the edit window closed so I couldn't fix the typo. There has to be an extra "n" because qs has to touch every element at least once so a baseline complexity of O(n) is unavoidable.
Hopefully, it didn't detract from the point that Knuth was talking about premature micro-optimizations and not design/architecture/algorithm optimization. Some inexperienced people are repeating "premature optimization" to try and win internet arguments instead of using it as nuanced advice to avoid wasting time.
True, though it's usually not worth the hassle. Most production implementations of quicksort just drop down to heapsort for the current sub-array if the stack gets too deep.
Hopefully, it didn't detract from the point that Knuth was talking about premature micro-optimizations and not design/architecture/algorithm optimization. Some inexperienced people are repeating "premature optimization" to try and win internet arguments instead of using it as nuanced advice to avoid wasting time.