Showing that a recurrence relation is O(n log n)

T (n) = T (xn) + T ((1 − x)n) + n = O(n log n)

where x is a constant in the range 0 < x < 1. Is the asymptotic complexity the same when x = 0.5, 0.1 and 0.001? What happens to the constant hidden in the O() notation. Use Substitution Method.

I'm trying to use the example on ~page 15 but I find it weird that in that example the logs change from default base to base 2. I also do not really understand why it needed to be simplified so much just so as to remove cnlog2n from the left side, could that not be done in the first step and the left side 开发者_如何转开发would just have "stuff-cnlog2n<=0" then evaulated for any c and n like so?

From what I tried it could not prove that T(n)=O(n)

Well, if you break this up into a tree using Master's theorem, then this will have a constant "amount" to calculate each time. You know this because x + 1 - x = 1.

Thus, the time depends on the level of the tree, which is logarithmic since the pieces are reducing each time by some constant amount. Since you do O(n) calcs each level, your overall complexity is O( n log n ).

I expect this will be a little more complicated to "prove". Remember that it doesn't matter what base your logs are in, they're all just some constant factor. Refer to logarithmic relations for this.

PS: Looks like homework. Think harder yourself!

This seems to me exactly the recurrence equation for the average case in Quicksort.

You should look at CLRS explanation of "Balanced Partitioning".

but I find it weird that in that example the logs change from default base to base 2

That is indeed weird. Simple fact is, that it's easier to prove with base 2, than with base unknown x. For example, log(2n) = 1+log(n) in base 2, that is a bit easier. You don't have to use base 2, you can pick any base you want, or use base x. To be absolutely correct the Induction Hypothesis must have the base in it: T(K) <= c K log_2(K). You can't change the IH later on, so what is happening now is not correct in a strict sense. You're free to pick any IH you like, so, just pick one that makes the prove easier: in this case logs with base 2.

the left side would just have "stuff-cnlog2n<=0" then evaulated for any c and n

What do you mean with 'evaluated for any c and n'? stuff-cnlog2n<=0 is correct, but how do you prove that there is a c so that it holds for all n? Okay, c=2 is a good guess. To prove it like that in WolframAlpha, you need to do stuff <= 0 where c=2, n=1 OK!, stuff <=0 where c=2, n=2OK!, stuff <= 0 where c=2, n=3OK!, ..., etc taking n all the way to infinity. Hmm, it will take you an infinite amount of time to check all of them... The only practical way (I can think of right now) for solving this is to simplify stuff-cnlog2n<=0. Or maybe you prefer this argument: you don't have WolframAlpha at your exam, so you must simplify.