algorithm

Question

.a                                    A nswer is  nlogn   by master method , but iam not able  to solve this equation by this method   can any one solve this and please tell me where iam wrong thanks

Answer 1

yes, your method is absolutely correct until this point. Just progress a bit more. See :

2^k T(1) = n T(1) = n

Now how many n's are added in the expression. If you count it, you got 3 n's for T(n/8). You could also check you got 2 n's for T(n/4). i.e you get k n's to add up for T(n/ 2^k)

Thus,

2 ^ k T(1) + n + n + n + ... = 2^k T(1) + k n = n T(1) + log n . n [ since, 2^k=n => k=log n]

                                                                     = n + n log n = n log n

Comments

ohh thanks bro , because of your solution  i cleared my 3 doubts in  recurrence relations thnks buddy :)))))))))))))))))))))