有一种基于比较的排序算法在O（n*log（sqrt（n））中运行。给定排序的Omega（n（log（n））下界的存在，这怎么可能呢？
基本上，这个问题要求你证明O（n*log（n））=O（n*log（√n）。记住√n=n^（1/2）和log（n^（1/2*log（n））。所以，现在我们有O（n*log（n））=O（1/2*n*log））。由于渐近表示法忽略了常数乘子，我们可以将其重写为O（n*log（n））=O（n*log（n））。沃伊拉，证明这是可能的。
对于基于比较的排序算法，可以绘制决策树。它是一个二叉树，表示算法所做的比较，这个树的每一个叶子都是给定集合中元素的排列。
有n个！可能的排列，其中n是集合的大小，并且其中只有一个表示排序的集合。通向每个叶的路径表示实现由该叶表示的排列所必需的比较。
现在让我们把h设为决策树的高度，l设为树叶的数量。输入集的每个可能的排列都必须在其中一个叶中，所以n<=l。高度为h的二叉树最多可以有2^h个叶子。因此我们得到了n<=l<=2^h。将对数应用于两边，因此得到h>=log（n！），log（n）是Omega（nlog（n））。
因为决策树的高度代表了到达叶子所需的许多比较，这证明了基于比较的排序算法的下界是nlog（n）。这再快不过了。因此，这个任务剩下的唯一正确的选项是假设Omega（nlog（n）也是Omega（nlog（sqrt（n））。log（sqrt（n））=log（n^（1/2））=（1/2）log（n）=>nlog。忽略const=1/2（因为我们对渐近复杂度感兴趣），就复杂度而言，你会得到nlog（sqrt（n））=nlog（n）。