CrazyEngineers
  • solve the recurrence eqn(time complexity) with detailed answer

    qwerty123

    qwerty123

    @qwerty123-ZuiVHD
    Updated: Oct 24, 2024
    Views: 1.2K
    a) T(n)=2T(n/2)+√n, n>=2
    T(1)=1
    b) T(n)= mT(n/2)+an^2
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies
  • nareshkumar6539

    MemberMay 1, 2012

    By using master slave method you can solve the recurrence relations easily
    T(n)=a T(n/b)+f(n) where a>1 b>0 f(n) is a function then
    here i am writing n to the power of log a base b as pow(n,log a base b)
    O is big o notation
    case 1:
    f(n) is O(pow(n,log a base b-E) where E>0 then T(n)=O(pow(n,log a base b))
    if you apply the above case to first recurrence relation time complexity is O(n)
    a=2,b=2 so log 2 base 2 value will be 1 .O(pow(n,1-E)) if we put E=1/3 then case 1 condition is satisfying.
    In master slave method 3 case are there check once,check it this answer is correct or not.
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register