solve the recurrence eqn(time complexity) with detailed answer

Replies

• 

  nareshkumar6539

  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.