# 2.47

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 :

${\displaystyle O(nlog({\sqrt {n}}))}$ and ${\displaystyle O(nlog(n))}$ belongs to same class of function with respect to Big O notation. There is no difference between them other than a constant factor.

${\displaystyle \lim _{x\to \infty }(nlog({\sqrt {n}}))/(nlog(n))}$ = ${\displaystyle \lim _{x\to \infty }1/2*(nlog(n))/(nlog(n))}$ = ${\displaystyle 1/2}$

Back to Chapter 2