- #1
Dragonfall
- 1,030
- 4
Can someone explain this "constructive induction" needed to solve recursive equations?
For example, use "constructive induction" to show that the following is [tex]\Theta (n)[/tex]
[tex]T(n) = 1 \leftrightarrow n = 1,2[/tex]
[tex]T(n) = T\lceil n/4\rceil + T \lceil 2n/3\rceil + \Theta (n) \leftrightarrow n > 2[/tex]
For example, use "constructive induction" to show that the following is [tex]\Theta (n)[/tex]
[tex]T(n) = 1 \leftrightarrow n = 1,2[/tex]
[tex]T(n) = T\lceil n/4\rceil + T \lceil 2n/3\rceil + \Theta (n) \leftrightarrow n > 2[/tex]
Last edited: