Change the assumptions of the proof.
The paper mentioned is "S. Skiena. Encroaching lists as a measure of presortedness. BIT, 28:775-784, 1988."
Other solution :
and belongs to same class of function with respect to Big O notation.
There is no difference between them other than a constant factor.
Back to Chapter 2