I'm brushing up on my Big O notation via 'Cracking the Code Interview', 6th Ed., and in the chapter on Big O notation, he poses in example 8 that comparison sorts are generally O(n*log(n)).
I wished to understand this derivation, and looked to the wikipedia page on comparison sort here, under the section "Number of comparisons required to sort a list", the article does the following:
By looking at the first
n/2
factors ofn!
, we get:log2(n!) >= log2((n/2)^(n/2))
I do not understand how this exponent was derived. The base makes sense to me since we're explicitly looking at the first n/2
factors, but I am failing to grasp how one might arrive at an exponent of n/2
.
Thank you for any and all explanations in advance!
To me, it makes sense after the fact, like if you already knew you were dealing with logarithms as a potentiality. I guess I should be considering that always as a possibility when attempting to derive the time complexity of an algorithm. I wrote out the first n/2
factors of 6!
as an example to myself.
6*5*4 = 120
(6/2)^(6/2) -> 3^3 = 27
And yeah, 120 >= 27, but still the reasoning behind the choice to use log2((n/2)^(n/2))
instead of another variation on a log escapes me still.
The goal of the derivation is to get a lower bound on the value of log(π!). There are obvious lower bounds, like log(1), log(π),...etc, just by omitting almost all factors in π! But we want to find a more tight lower bound. The approach that is taken here, is to eliminate half of the factors in π!, namely the smaller ones. So first write out π! with all its π factors:
Β Β Β π! = π(πβ1)(πβ2) ... (βπ/2β+1)(βπ/2β)(βπ/2ββ1) ... (3)(2)(1)
Then omit the second half of these factors to keep only the first βπ/2β factors, so that surely we arrive at a value that is not greater than the original:
Β Β Β π! β₯ π(πβ1)(πβ2) ... (βπ/2β+1)
We continue to simplify it more by replacing these factors all by βπ/2β, so that we get βπ/2β factors that are all the same. Again this expression can not be greater than what we already had, as we replaced each factor (if any) with a smaller one (From now on π/2 is short for βπ/2β):
Β Β Β π! β₯ (π/2)(π/2)(π/2) ... (π/2)
which is the same as saying:
Β Β Β π! β₯ (π/2)π/2
Back to the log2(π!) we started with. As the logarithm is an always increasing function, we can apply the logarithm to both sides of the comparison:
Β Β Β log2π! β₯ log2[(π/2)π/2]
Not your question, but the reasoning continues by applying some of the logarithmic properties:
Β Β Β log2π! β₯ (π/2)log2(π/2)
Β Β Β log2π! β₯ (π/2)(log2π β log22)
Β Β Β log2π! β₯ (π/2)(log2π β 1)
Β Β Β log2π! β₯ (π/2)log2π β π/2
Let's take π=12, then π! is 479001600, which is 12β 11β 10β 9β 8β 7β 6β 5β 4β 3β 2β 1
If we only keep the first half of these factors in the product, we surely get a smaller result:
Β Β Β 12β 11β 10β 9β 8β 7
The second step was to replace the remaining factors with π/2, so we reduce even more to get this:
Β Β Β 6β 6β 6β 6β 6β 6
As we made all factors smaller than they were, we surely get a smaller product, i.e. 46656
This remains true if we apply the logarithm to both the original value (π!) and this value ((π/2)π/2):
Β Β Β log2(12!) = 28.8354552341...
and
Β Β Β log2(66) = 15.5097750043...