1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to find upper bound for recurrence relation

  1. Apr 24, 2016 #1
    1. The problem statement, all variables and given/known data
    Find a tight upper bound for the recurrence relation using a recursion tree argument

    2. Relevant equations
    T(n)=T(n/2)+T(n/3)+c

    3. 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?
     
  2. jcsd
  3. Apr 24, 2016 #2
    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 ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to find upper bound for recurrence relation
  1. Find an upper bound (Replies: 6)

Loading...