• Support PF! Buy your school textbooks, materials and every day products Here!

Constructive Induction

  • Thread starter Dragonfall
  • Start date
1,028
4
1. Homework Statement
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 [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]


3. The Attempt at a Solution

I keep getting exponential for lower and upper bounds.
 

Answers and Replies

Related Threads for: Constructive Induction

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
3
Views
6K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
768
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
1K
Top