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.

  • 0
    What is lgn ,nlgn and clgnn2012-08-06
  • 0
    @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.2012-08-06
  • 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