How to solve this recurrence T(n)=2T(n/5)+3T(n/10)+n

Question

i need to solve the teta notation for $T(n)=2\cdot T(\frac{n}{5})+3\cdot T(\frac{n}{10})+n $ but the recursive calls each one multiplied by a different factor make it not solvable with the master theorem , and I can't figure out how the recursive tree will look like.

Thanks in advance.

Answer 1

We Show that a solution is $$T(n)=\frac{10n}{3}$$ then we have $$2\cdot T(\frac{n}{3})=2\cdot \frac{10}{3}\cdot \frac{n}{5}=\frac{4}{3}n$$ $$3\cdot T(\frac{n}{10})=3\cdot \frac{10}{3}\cdot \frac{n}{10}=n$$ so we have $$\frac{4}{3}n+n+n=\frac{10n}{3}$$