How to solve the recursive complexity T(n) = T(n/3)+T(2n/3)+cn

Question

When calculate the median, we know that if we break the input array into subgroups as five and solve it recursively, we will get O(n) complexity, but if we break the array into 3, it won't return the O(n) complexity.

Does any one know how to prove it?

Answer 1

It' gonna be nlg(n) .
Try to draw it's recursion tree : The total cost of each level is equal to n, and the depth of this tree is lg(n) .
Note : Actually it's depth is between log(n) base 3 and log(n) base 3/2, but since the order of logarithms in all bases are same, we can just consider it as lg(n).

Answer 2

It looks like the recurrence in the title is wrong, but I think the Master Theorem for solving recurrences will be handy. You can show that going from one denominator to another puts you into a different case which goes from O(n) to something worse.