## Constructive Induction

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$$
 Anyone? This is kinda urgent.

Recognitions:
Gold Member
Staff Emeritus
 Quote by 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$$
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$.

## Constructive Induction

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