1

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.

Kevin Carlson
  • 52,457
  • 4
  • 59
  • 113
Rambo
  • 11
  • 2
  • What is lgn ,nlgn and clgnn – Argha Aug 06 '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 06 '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. –  Aug 08 '12 at 03:30

3 Answers3

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

marty cohen
  • 107,799
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$.

DanielV
  • 23,556
  • 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 06 '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 06 '15 at 22:02
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?

t.b.
  • 78,116
Rambo
  • 1