Constructive Induction

1. Apr 22, 2008

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

Last edited: Apr 22, 2008
2. Apr 22, 2008

Dragonfall

Anyone? This is kinda urgent.

3. Apr 23, 2008

HallsofIvy

Staff Emeritus
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$.

4. Apr 23, 2008

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

Last edited: Apr 23, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook