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:

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

-
You got the reasoning with the signs backwards at the end. Surely $C=1$ does not work since one wants $4n\ln n\le(4C-3)(n\ln n+3n\ln4)$, but $C\ge7/4$ might work, depending on the first steps of the induction. – Did Jun 6 '15 at 17:20
@Did Thank you for noticing! That's an embarassing mistake haha, but I believe I have fixed it now. $C \ge 7/4$ isn't actually large enough as $n > 4^{7/3}$ will defy the inequality (well the one I derived, I'm not sure how to derive the one you commented). But $C \ge 4$ does hold no matter how large $n$ gets, and it seems to be the lowest possible bound. Btw, I'm curious why you were browsing such an old and relatively uninteresting problem, is it some kind of moderator responsibility? – DanielV Jun 6 '15 at 22:02

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

-

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?

-
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