1
$\begingroup$

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.

  • 1
    @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](http://en.wikipedia.org/wiki/Logarithm#Particular_bases) too.2012-08-08

3 Answers 3

1

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

1

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

  • 0
    @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?2015-06-06
0

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?

  • 0
    I'm stuck on the first line. How did you get the $T(/n/4)$ factor after the $n\lg n$ term?2012-08-07