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.

-
What is lgn ,nlgn and clgnn –  Argha Aug 6 '12 at 18:39
@Ranabir. Customarily, $\lg n$ is used to denote the log to the base 2 of $n$. There are still problems with the post and its edited form. It's not at all obvious what Rambo intends here. –  Rick Decker Aug 6 '12 at 18:47
@Rick When I learned math as a kid, we had to walk to school 10 miles uphill both ways, and $\lg$ was base 10 logarithm. Not kidding about the last part. It's the ISO notation too. –  user31373 Aug 8 '12 at 3:30

$$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:

$$n \log n \le C \cdot \left(n \log n - \underbrace{\frac 34 n \log \frac n4}_{\text{subtracted term}}\right)$$

So we can see that as long as the subtracted term is positive, we can satisfy the equation with $C=1$. The term is positive for $\frac n4 > 1 \rightarrow n > 4$, so we have that

$$(\exists C>0, n_0>0)(\forall n > n_o)\, T(n) \le C \cdot n \log n$$

is satisfied for $C=1$ and $n_0 = 4$.

-

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)$.

-
\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?
I'm stuck on the first line. How did you get the $T(/n/4)$ factor after the $n\lg n$ term? –  Rick Decker Aug 7 '12 at 14:36