-1

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.

Vasili
  • 10,690
Matan Halfon
  • 1
  • 1
    Thus, a very good occasion to forget the so called Master theorem and the recursive trees and to start thinking. First, if every $T(n)$ is noonegative, $T(n)\geqslant n$. Second, find some values of $c$ such that the property $T(n)\leqslant cn$ is hereditary (you should get that every $c\geqslant10/3$ works). Conclusion: for some fixed $c$ large enough, $n\leqslant T(n)\leqslant cn$ for every $n$, in particular, $T(n)=\Theta(n)$. – Did Mar 29 '18 at 14:49

1 Answers1

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}$$

Dr. Sonnhard Graubner
  • 95,283