[Math] How to solve Recurrence relation: $T(n) = T(n/3) + T(n/5) + n$

algorithmsrecurrence-relationsrecursion

Given the following: $T(n) = T(n/3) + T(n/5) + n$

The aim is to find the upper bound of this solution.

I have tried to solve this using Master's Theorem, but this does not apply for this problem.

My next best options would be Substitution or Iteration, but I am having troubles finding examples similar enough to follow these methods to solve this relation.

If I were to make a "guess" to use for substitution method I would use $T(n) \leq cn$ but after working through the problem I am unable to reach any sort of a solution

Best Answer

Let's check if \begin{equation} T(n) = \frac{15}{7}n \end{equation} is a solution for our recursion. \begin{align} T(n) &= \frac{15}{7}n \\ T(\frac{n}{3}) &=\frac{1}{3} \frac{15}{7}n\\ T(\frac{n}{5}) &=\frac{1}{5} \frac{15}{7}n \end{align} So \begin{equation} T(\frac{n}{3}) + T(\frac{n}{5}) + n = \frac{1}{3} \frac{15}{7}n + \frac{1}{5} \frac{15}{7}n + n \end{equation} which is \begin{equation} T(\frac{n}{3}) + T(\frac{n}{5}) + n = \frac{3}{7}n + \frac{5}{7}n + n = \frac{8+7}{7}n = \frac{15}{7}n = T(n) \end{equation} So \begin{equation} T(n) = \frac{15}{7}n \end{equation} is indeed a solution.

Related Question