Constructive Induction

  • Thread starter Dragonfall
  • Start date
1,028
4

Main Question or Discussion Point

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

1,028
4
Anyone? This is kinda urgent.
 
HallsofIvy
Science Advisor
Homework Helper
41,734
893
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].
 
1,028
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 for: Constructive Induction

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