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

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.