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