Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
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 too. –  user31373 Aug 8 '12 at 3:30

3 Answers 3

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

share|improve this answer

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

share|improve this answer
    
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 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 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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.