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

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

$$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? Jun 6 '15 at 22:02

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? Aug 7 '12 at 14:36