How to solve the recursive complexity T(n) = T(n/4

问题:

I am solving this recurrence using a recursion tree. The total cost of each level is n, and the depth of the tree is between log (n) base 4 and log (n) base 4/3. Intuitively, I expect the solution to be at most the number of levels times the cost at each level. O(cn log (n) base 4/3) = O(n log n). I was wondering if my approach towards the problem, and my solution is correct?

回答1:

Think of it this way: for the first log₄ n layers of the recursion tree, the sum of the work across those layers will be cn, because if you sum up the total sizes of all the subproblems, it should total n so the total work is cn. This means that the work done is Ω(n log n).

You can upper-bound the work done by pretending that the sum of the work done in each layer of the tree is O(n) (it actually drops off as you go lower and lower in the tree, so this is an upper bound) and the height is log_4/3 n. This gives an upper bound on the work of O(n log n).

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

Hope this helps!

回答2:

Edited: Was missing the OP and answered a wrong solution, below is my refined attempt

Intuitively, You are right.

For a more formal approach, you can proof it mathematically.

The magic trick is here: Akra-Bazzi theorem which is a more general version of master theorem

For the relation T(n) = T(n/4) + T(3n/4) + cn

We got g(n) = cn, k = 2, a1 = a2 = 1, b1 = 1/4, b2 = 3/4

By the theorem, we have to solve p for a1b1^p + a2b2^p = 1 which is obviously p = 1

Then T(n) = O(n^p * (1+integration(1/n dn))) = O(n*(1+log(n))) = O(nlogn)

which match our guess