solve the recurrence eqn(time complexity) with detailed answer

qwerty123

qwerty123

@qwerty123-ZuiVHD Oct 24, 2024
a) T(n)=2T(n/2)+√n, n>=2
T(1)=1
b) T(n)= mT(n/2)+an^2

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

CrazyEngineers powered by Jatra Community Platform

  • nareshkumar6539

    nareshkumar6539

    @nareshkumar6539-BKuVbx May 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.