lower bound in sorting algorithm

algorithm
bound
in
lower
sorting

#1

In geeksforgeeks.com there is an interesting fact about the lower bound of the sorting algorithm .
the link is :----
http://www.geeksforgeeks.org/lower-bound-on-comparison-based-sorting-algorithms/

please explain this part which I felt a tricky part —

 n!  <= 2^x

 Taking Log on both sides.
      \log_2n!  <= x

 Since \log_2n!  = \Theta(nLogn),  we can say
      x = \Omega(nLog_2n)

#2

Well. You know that maximum number of leaves in binary tree with height x is 2^x. And your decision tree must have at least n! leaves so n! <= 2^x.

From that you have inequality log n! <= x (I will omit the 2 in logarithm. Firtsly it’s nicer, secodly it doesn’t matter).

Now we need two estimations for value of n!. First, we know, that n^n >= n!, that’s easy to see, because we have product of n numbers and all are bigger than n. Also we know, that n! >= (n/2)^(n/2). If you write first n/2 elements of n! they are all bigger than n/2, so inequality holds.

n^n >= n! >= (n/2)^(n/2)

But logarithm holds inequalities. So log(n^n) >= log(n!) >= log((n/2)^(n/2)). And because log(a^b) = b.log(a) then n.log(n) >= log(n!) >= (n/2).log(n/2). But in O-notation both left and right side is O(n.log(n)). And because log(n!) is both bigger and smaller than O(n.log(n)) it must be eqaul to it.

From that we know, that O(log(n!)) = O(n.log(n)). (And same from theta or omega). So every sort based on comparison must have time complexity at least n.log(n).


#3

I got the explanation ,but how n!<=2^x . kindly give the example with a decision tree.


#4

something is here even with picture.

You must realize, that full binary tree has double of vertices on the next layer. So in height 0 it has 1=2^0 vertex, on height 1 two vertices, height 2 four vertices, height 3 eight verticed and so on. So in height x it has 2^x vertices.