Solving the recurrence T(n) = T(n / 1000) + T(999n/1000) + cn?

Question

What is the solution of this recurrence?

T(n) = T(n/1000) + T(999n/1000) + cn.

I think its O(n log n) since the work done per level is going to be cn and the height of the tree will be log n to the base of 1000/999, but I'm not sure if the reasoning is valid. Is that correct?

Answer 1

One thing to notice is that for the first log₁₀₀₀n layers, all branches of the recursion will be active (i.e. the branches for the n / 1000 cases won't have bottomed out) and the work done per layer will be Θ(n). This gives you an immediate lower bound on the runtime as Ω(n log n), since there are Θ(log n) layers doing Θ(n) work each.

For layers below that, the work begins to drop off because the branches for the n / 1000 case will bottom out. However, you can upper bound the work done by pretending that each layer in the tree will do Θ(n) work. In that case, there will be log_1000/999 n layers before the 999n/1000 case bottoms out, so you get an upper bound of O(n log n) because you have Θ(log n) layers doing Θ(n) work each.

Since the work done is Ω(n log n) and O(n log n), the runtime is Θ(n log n).

Hope this helps!