Q:

Solving Log equation using master theorem

I`m studying Master Theorem, and I got stuck in the case 3. The example is :
T(n) = 3T(n/4) + nlogn.
I have no idea how my teacher got the final value, c = 3/4, based on the equation below :
3*[n/4 * log(n/4)] <= c * nlogn. 
On the internet, I found the same example but with no real explanation on the resolution : (slide 26)
http://www.cs.bgu.ac.il/~ds142/wiki.files/Presentation02[2].pdf
Can someone explain me step by step ?
Thanks

A:

There  is another  closely  related recurrence  that  admits an  exact
solution.  Suppose we  have  $T(0)=0$ and  $T(1)=T(2)=T(3)=1$ and  for
$n\ge 4$
$$T(n) = 3 T(\lfloor n/4 \rfloor) + n \lfloor \log_4 n \rfloor.$$
It seems reasonable to use integer  values here as the running time of
an algorithm is a function of discrete quantities.
Furthermore let the base four representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_4 n \rfloor} d_k 4^k.$$
Then  we can  unroll the  recurrence to  obtain the  following exact
formula for $n\ge 4$
$$T(n) = 3^{\lfloor \log_4 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_4 n \rfloor -1} 
3^j \times (\lfloor \log_4 n \rfloor - j) \times 
\sum_{k=j}^{\lfloor \log_4 n \rfloor} d_k 4^{k-j}.$$
Now to get  an upper bound consider a string of  value three digits to
obtain
$$T(n) \le 3^{\lfloor \log_4 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_4 n \rfloor -1} 
3^j \times (\lfloor \log_4 n \rfloor - j) \times 
\sum_{k=j}^{\lfloor \log_4 n \rfloor} 3 \times 4^{k-j}.$$
This simplifies to
$$(16 \lfloor \log_4 n \rfloor - 48) \times 
4^{\lfloor \log_4 n \rfloor}
+ \frac{193}{4} \times 3^{\lfloor \log_4 n \rfloor}
+ \frac{1}{2} \lfloor \log_4 n \rfloor + \frac{3}{4}.$$
This bound is actually attained and cannot be improved upon, just like
the lower bound,  which occurs with a one digit  followed by zeroes to
give
$$T(n) \ge 3^{\lfloor \log_4 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_4 n \rfloor -1} 
3^j \times (\lfloor \log_4 n \rfloor - j) \times 
4^{\lfloor \log_4 n \rfloor-j}.$$
This simplifies to
$$ (4 \lfloor \log_4 n \rfloor - 12) \times 4^{\lfloor \log_4 n \rfloor}
+ 13 \times 3^{\lfloor \log_4 n \rfloor}.$$
Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\lfloor \log_4 n \rfloor \times
4^{\lfloor \log_4 n \rfloor}
\in \Theta\left(\log_4 n \times 4^{\log_4 n}\right) 
= \Theta\left(\log n \times n\right).$$
Observe that there is a lower order term
$$3^{\lfloor \log_4 n \rfloor}
\in \Theta\left(4^{\log_4 3 \times \log_4 n}\right) 
= \Theta\left(n^{\log_4 3}\right).$$
This term represents the  asymptotics being generated by the recursive
term in the recurrence.
These are both in agreement with what the Master theorem would produce.
This MSE link I may be relevant as may be this MSE link II.

