Recurrence substitution method I  just want to see if I did this right. I need to show that $T(n) = 3T(n/4) + n\log n$ 
shows that $T(n) = O(n\log n)$ using substitution method in recurrence.
$$T(n) = 3c(n/4 \log n/4) + n\log n$$
$$c\log nn - cn + n\log n$$
$$n\log n$$
That does not seem right but I followed an example and thats how it turned out. Thanks for any help with this.
 A: Suppose
$T(m) 
< c m \log m
$
for
$m < n$
(this is called strong induction
since it depends on
all preceding values,
not just the
immediately preceding value).
Then
$\begin{align}
T(n)
&= 3 T(n/4) + n \log n\\
&< 3 c (n/4) \log(n/4) + n \log n\\
&= 3 c (n/4) (\log(n)-\log(4)) + n \log n\\
&= (3 c n/4) \log(n)-(3 c n/4) \log(4) + n \log n\\
&< (3 c/4+1) n \log(n)\\
\end{align}
$
If
$3 c/4+1 < c$,
then
$T(n) < c n \log n$.
This is true if
$c > 4$.
So,
once we find a $c > 4$
such that
$T(n) < c n \log n$
for some initial values of $n$,
then
$T(n) < c n \log n$
for all larger values values of $n$.
To do this,
just choose any
$c >
\max(4, T(2)/(2 \log 2), T(3)/(3 \log 3))
$.
Then $T(n) < c n \log n$
for all $n$,
so $T(n) = O(n \log n)$.
A: $$T(n) \in O(n \log n)$$
is defined as 
$$(\exists C>0, n_0>0)(\forall n > n_o)\, T(n) \le C \cdot n \log n$$
Given that $T(n) = 3\,T\left(\frac n4\right) + n \log n$, we need to find $C$ and $n_0$ to satisfy the definition.  Let's proceed inductively:
$$T(n) \le C \cdot n \log n$$
$$3\,T\left(\frac n4\right) + n \log n \le C \cdot n \log n$$
Now we see that we need to borrow the inductive hypothesis $T\left(\frac n4\right) \le C \cdot \frac n4 \log \frac n4$.  Thus the above statement would be implied by:
$$3\,\left(C \cdot \frac n4 \log \frac n4\right) + n \log n \le C \cdot n \log n$$
So now if we can find a positive $C$ that makes the above statement true for sufficiently large positive $n$, then we have satisfied the desired definition.  Move things around a bit:
$$3~C~n~\log n  -  3~C~n~\log 4  +  4~n~\log n  \le  4~C~n~\log n$$
$$4 \le \frac{3~C~\log 4} {\log n } + C$$
$$\frac{4 \log ~ n}{\log n + 3~\log(4)} \le C$$
We can see that the left hand side will never be as large as $4$ (let $n = 4^z$ and simplify to make it more clear), so $C \ge 4$ satisfies the inequality for sufficiently large $n$.
A: Does this look right? 
$$\begin{align*}T(n) &= 3T\left(\frac{n}{4}\right)+n \log n T\left(\frac{n}{4}\right) \\
 & = 3T\left(\frac{n}{16}\right)+\frac{n}{4} \log\left(\frac{n}{4}\right) T(n) \\
& = 3\left[3T\left(\frac{n}{16}\right)+\frac{n}{4} log\left(\frac{n}{4}\right)\right]+n\log n \\
& = 9T\left(\frac{n}{16}\right) + \frac{3n}{4}log\left(\frac{n}{4}\right)+n\log n \\ & \lt  9T\left(\frac{n}{16}\right) + \left(\frac{3n}{4}\right) \log n + n \log n \\
& = 9T\left(\frac{n}{16}\right) + \left(\frac{7n}{4}\right) \log n \end{align*}$$
which then ends up as $n\log n$ right?
