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)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).
I got the explanation ,but how n!<=2^x . kindly give the example with a decision tree.
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.