Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Constructive Induction

  1. Apr 22, 2008 #1
    Can someone explain this "constructive induction" needed to solve recursive equations?

    For example, use "constructive induction" to show that the following is [tex]\Theta (n)[/tex]

    [tex]T(n) = 1 \leftrightarrow n = 1,2[/tex]
    [tex]T(n) = T\lceil n/4\rceil + T \lceil 2n/3\rceil + \Theta (n) \leftrightarrow n > 2[/tex]
    Last edited: Apr 22, 2008
  2. jcsd
  3. Apr 22, 2008 #2
    Anyone? This is kinda urgent.
  4. Apr 23, 2008 #3


    User Avatar
    Staff Emeritus
    Science Advisor

    Since you haven't said what [itex]\Theta(n)[/itex] is, I don't see how any method can "prove" that is [itex]\Theta(n)[/itex].

    Whatever [itex]\Theta(n)[/itex] is, T(3) is definitely not equal to [itex]\Theta(3)[/itex], it is equal to [itex]\Theta(3)+ 2[/itex].
  5. Apr 23, 2008 #4
    [tex]\Theta (n)[/tex] in the recurrence is "some function" in the complexity class [tex]\Theta (n)[/tex].

    The complexity class [tex]\Theta (n)[/tex] is the intersection of [tex]O(n)[/tex] and [tex]\Omega (n)[/tex].
    Last edited: Apr 23, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Constructive Induction
  1. Constructing a triangle (Replies: 13)

  2. Constructing a function (Replies: 13)

  3. The construction of pi (Replies: 6)