Homework Help: Constructive Induction

1. Apr 22, 2008

Dragonfall

1. The problem statement, all variables and given/known data
I'll try my luck here: 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$$

3. The attempt at a solution

I keep getting exponential for lower and upper bounds.