Solve T(n) = T(n/3) + T(2n/3) + n. Give matching upper and lower bounds and justify both.

Solve T(n) = T(n/3) + T(2n/3) + n. Give matching upper and lower bounds and justify both.

Approach: Draw the recursion tree, note the work per level, then bound the tree depth from the shallowest and deepest root-to-leaf paths separately.

Theta(n log n). Every level of the recursion tree costs at most n, because the subproblem sizes at one level sum to n until branches start bottoming out. The deepest root-to-leaf path repeatedly takes the 2/3 branch and has length log_{3/2} n, giving the upper bound n log_{3/2} n = O(n log n). The shallowest path takes the 1/3 branch every time and has length log_3 n, and every level above that depth costs exactly n, giving the lower bound n log_3 n which is Omega(n log n). Substitution confirms it: assuming T(m) <= c m log m for all m < n gives T(n) <= c(n/3)log(n/3) + c(2n/3)log(2n/3) + n, which simplifies to c n log n - c n (log 3 - 2/3) + n and stays under c n log n once c is large enough. The unbalanced split therefore costs only a constant factor over an even one, and the tree depth is what that constant measures.

Follow-up: At what split ratio does the depth become large enough that the recurrence stops being Theta(n log n)?

Key concepts: recursion tree, unbalanced split, tree depth, substitution.