Constructive Induction

  • Thread starter Dragonfall
  • Start date
  • #1
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]
 
Last edited:

Answers and Replies

  • #2
1,030
4
Anyone? This is kinda urgent.
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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]
Since you haven't said what [itex]\Theta(n)[/itex] is, I don't see how any method can "prove" that is [itex]\Theta(n)[/itex].

Whatever [itex]\Theta(n)[/itex] is, T(3) is definitely not equal to [itex]\Theta(3)[/itex], it is equal to [itex]\Theta(3)+ 2[/itex].
 
  • #4
1,030
4
[tex]\Theta (n)[/tex] in the recurrence is "some function" in the complexity class [tex]\Theta (n)[/tex].

The complexity class [tex]\Theta (n)[/tex] is the intersection of [tex]O(n)[/tex] and [tex]\Omega (n)[/tex].
 
Last edited:

Related Threads on Constructive Induction

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
13
Views
4K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
2K
Replies
1
Views
1K
Top