Answer to Question #275965 in Algorithms for Mark

Question

T(n) = T(n/3) + T(2n/3)+ big O(n)

Find the upper bound of this recurrence equation with the help of recursion tree

Answer 1

The most shallow branch of the recursion tree is the leftmost branch. Its length is $log_3n$

The deepest branch of the recursion tree is the rightmost one, and its depth is $log_{3/2}n$

On each level of the tree the total size of the subproblems is at most n

So,

$T\le nlog_{3/2}n$