یه روش راحت برای حل این مسله بصورت سر انگشتی اینه:
عناصر مرتب شده یعنی اینکه عناصر بترتیب سر جاشون هستن . به تعبیری شما باید بدونید که هر عنصری از عناصر قبلی اش بزرگتر و از عناصر قبلیش کوچکتره از اونجایی که تعداد عناصر n هستش پس شما n تا پیمایش داری برای هر عنصر , و برای اینکه بدونی هر عنصر در سر جای درستش هست میشه از یک الگوریتم مثله جستجوی دودیی که از مرتبه log n هستش استفاده کرد که در کمترین حالت همون nlgn میشه . ولی در حالت کلی به این اثبات نمی گین ولی کمک می کنه بفهمی چرا کمتر از nlgn نمیشه .