1

I've read on an online forum that one of the methods to solving the recursive relation $\;T(n) = T(n/3) + T(2n/3) + n\;$ is to apply the master's theorem.

It says that we can first solve $\;T(n/3) + n\;$ and use its answer in $\;T(n)\;$ ( https://www.quora.com/How-do-I-solve-this-recurrence-T-n-T-n-3-T-2n-3-n ) .

For $\;T(n/3) + n,\;\;a = 1,\;b = 3\;$ and $\;c = 1\;.$

And since $\;c >\dfrac{\log a}{\log b}\;,\;\;T(n/3) + n = O(n)\;.$

Then, by solving $\;T(n) = T(2n/3) + O(n)\;$ with the same method, we have $\;T(n) = O(n)\;.$

I would like to know whether this is correct? Since it's like the person who gave the answer is treating $\;T(n/3)\;$ and $\;T(2n/3)\;$ as two separate functions.

Angelo
  • 12,328
NewbieToCoding
  • 123
  • $O(n)$ looks too slow, though $O(n^{1+\epsilon})$ may (eventually) be true for any positive $\epsilon$ – Henry Apr 11 '21 at 14:54

0 Answers0