n varies with the input as well :) But yes, since ρ is bounded by n you can reduce the complexity to O(n log n) again, but i think the important part here is to distinguish the complexity against other sorting algorithms and Timsort improves things for specific inputs as they note.