Geek asks and answers

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

I will solve this repetition using the recursion tree. The total cost of each level is n, and the depth of the tree is between log (n) base 4and log (n) base 4/3. Intuitively, I expect that the solution will be no more than the number of levels that will cost at each level. O(cn log (n) base 4/3) = O(n log n). I was wondering if my approach to the problem is right and my solution is right?

+3
source share
2 answers

Think of it this way: for the first log 4n layers of a recursion tree the sum of the work on these layers will be cn, because if you sum the total sizes of all the subtasks, it must be equal to n, so the total work will be cn. This means that the work is done & Omega; (n log n).

You can do the top job by pretending that the amount of work performed in each layer of the tree is O (n) (it actually drops when you go lower and lower in the tree, so this is the upper bound), and the height is log 4/3n This gives an upper bound on the performance of O (n log n).

Since the work is done & Omega; (n log n) and O (n log n), the job was done more correctly & Theta; (n log n).

Hope this helps!

+1
source

Edited: I skipped the OP and answered the wrong decision, below is my refined attempt

Intuitively, you are right.

.

: -,

T(n) = T(n/4) + T(3n/4) + cn

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

p a1b1^p + a2b2^p = 1, , , p = 1

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

0

More articles:


All Articles