1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recurrence by Induction

  1. Sep 15, 2009 #1
    Prove the following recurrence by induction
    T(n) = 2T(n/2) + n lg n = Θ ( n lg^2 n ), T(1) = 1

    This to me looks scary and I was wondering if anybody had a heads up on how to solve for this
     
  2. jcsd
  3. Sep 16, 2009 #2

    CEL

    User Avatar

    Suppose T(n) is true. From that supposition show that T(n+1) is true. That is the proof by induction.
     
  4. Sep 16, 2009 #3
    Not forgetting to prove T(1) to be true first as well.
     
  5. Sep 16, 2009 #4

    CEL

    User Avatar

    T(1) is assumed to be 1, by the hypothesis.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Recurrence by Induction
Loading...