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

How to find upper bound for recurrence relation

  • Thread starter ciphone
  • Start date
  • #1
3
0

Homework Statement


Find a tight upper bound for the recurrence relation using a recursion tree argument

Homework Equations


T(n)=T(n/2)+T(n/3)+c

The Attempt at a Solution


I don't know how to do this problem because the tree doesn't have symmetry. One side of the tree can keep going because of the lack of symmetry plus at the end there is no way that you get T(1). How do you solve this problem using a recursion tree?
 

Answers and Replies

  • #2
535
72
I don't understand.
If one consider that the indexation of sequence ##T(n)## is in ##\mathbb{N}-\{0\}##, then the index ##n## must be a multiple of ##6##, since 2 and 3 are mutually prime divisors of ##n##.

At first sight you must consider a sequence of type ##T(6n) = T(3n) + T(2n) + c ##. But for 6 to divide ##3n## and ##2n##, it must divide ##n##. It leads you to consider the sequence ##T(36n) = T(18n) + T(12n) + c ##.

With that, what sense do you give to ##T(n)## for indexes that are not multiple of 12 and 18 ?
 

Related Threads on How to find upper bound for recurrence relation

  • Last Post
Replies
6
Views
1K
Replies
5
Views
2K
Replies
2
Views
14K
  • Last Post
Replies
6
Views
777
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
881
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
1
Views
831
Replies
3
Views
470
Replies
4
Views
2K
Top