Master theorem with logn

Question

Here's a problem.

I am really confused about the c being equal to 0.5 part. Actually overall I am confused how the logn can become n^(0.5). Couldn't I just let c be equal to 100 which would mean 100 < d which results in a different case being used? What am I missing here?

Answer 1

You of course could set c = 100 so that n^c is a (very, veeery) rough asymptotical upper bound to log(n), but this would give you a horrendous and absolutely useless estimate on your runtime T(n).

What it tells you, is that: every polynomial function n^c grows faster than the logarithm, no matter how small c is, as long as it remains positive. You could take c=0.0000000000001, it would seem to grow ridiculously small in the beginning, but at some point it would become larger than log(n) and diverge to infinity much faster than log(n) does. Therefore, in order to get rid of the n^2 log(n) term and being able to apply the polynomial-only version of the Master theorem, you upper bound the logarithmic term by something that grows slowly enough (but still faster than log(n)). In this example, n^c with c=0.5 is sufficient, but you could also take c=10^{-10000} "just to make sure".

Then you apply the Master theorem, and get a reasonable (and sharp) asymptotic upper bound for your T(n).