Replies
Welcome, guest
Join CrazyEngineers to reply, ask questions, and participate in conversations.
CrazyEngineers powered by Jatra Community Platform
-
@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.