1) + T(n/2) + n

 

for the relation

T(n) = T(n-1) + T(n/2) + n

can I first solve the term (T(n-1) + n) which gives O(n^2), then solve the term T(n/2) + O(n^2) ?

according to the master theorem which also gives O(n ^ 2) or it is wrong?

No, you cannot solve it using Mater-theorem.

You need to solve it using Akra–Bazzi method, a cleaner generalization of the well-known master theorem.

  • Master-theorem assumes that the sub-problems have equal size.

  • The master theorem concerns recurrence relations of the form

    • T(n) = a T(n/b) + f(n) , where a>=1, b>1.

    I am not deriving here the steps for the solution so that you work out on it. If you have further problem while solving the same, please comment below. Good luck...

    I don't think your approach is correct in the general case. When you throw away the T(n/2) term to calculate the complexity of the T(n-1) term you end up underestimating the size of the T(n-1) term.

    For a concrete counterexample: 

     T(n) = T(n-1) + T(n-2) + 1

    Your technique is also going to come up with T(n) = O(n^2) for this but the real complexity is exponential.

    链接地址: http://www.djcxy.com/p/26488.html

    上一篇: 为什么我们需要Scala的CanBuildFrom中的From类型参数

    下一篇: 1）+ T（n / 2）+ n