What is constructive induction and how is it used to solve recursive equations?

[Dragonfall]

Can someone explain this "constructive induction" needed to solve recursive equations?

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

T(n) = 1 \leftrightarrow n = 1,2
T(n) = T\lceil n/4\rceil + T \lceil 2n/3\rceil + \Theta (n) \leftrightarrow n > 2

 

[Dragonfall]

Anyone? This is kinda urgent.

 

[HallsofIvy]

Can someone explain this "constructive induction" needed to solve recursive equations?

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

T(n) = 1 \leftrightarrow n = 1,2
T(n) = T\lceil n/4\rceil + T \lceil 2n/3\rceil + \Theta (n) \leftrightarrow n > 2

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

Whatever \Theta(n) is, T(3) is definitely not equal to \Theta(3), it is equal to \Theta(3)+ 2.

 

[Dragonfall]

\Theta (n) in the recurrence is "some function" in the complexity class \Theta (n).

The complexity class \Theta (n) is the intersection of O(n) and \Omega (n).