0

How can I approach recurrence relations such as the following, where the recurrence is being broken down into 1-2 different terms? I'm also not sure if I phrased this right so correct me if I'm wrong.

e.g. something like the following: $T(n) = T(\frac{n}{2}) + T(\frac{n}{3})$

My current thoughts are to start by drawing it out for a small case, but then I get a little stuck/confused on how to build it back up.

Also, are there any general resources or advice for building intuition on recurrence relations? I feel like I'm lacking the intuition to truly understand recurrences and this is not the first time this is happening (I also struggled in another math course which had a few recurrences), so I'd like to have a more complete understanding of the topic. If you know something that might help, it'd be great. Thanks!

Revise
  • 101
  • The example of recurrence you give is unclear. How would you compute $T(n)$ for $n \in \mathbb{N}$? There must be a simple way to begin with initial values and compute all other values using the recurrence relation. – Jean-Armand Moroni Sep 01 '22 at 16:32

1 Answers1

1

Hint.

Regarding the recurrence

$$ T(n) = T\left(\frac na\right)+T\left(\frac nb\right) $$

with $a,b$ relative primes you can try to make $n=a^jb^k$ and after substitution we have

$$ T(a^jb^k) = T(a^{j-1}b^k)+T(a^jb^{k-1}) $$

or equivalently

$$ R(j,k) = R(j-1,k) + R(j,k-1) $$

which can be easily solved with characteristic functions, assuming $A(x,y) = \sum_{j,k}^nR(j,k)x^jy^k$

Cesareo
  • 33,252