# Calculate the complexity of a recursive algorithm?

Posted 6 months ago
983 Views
|
5 Replies
|
0 Total Likes
|
 Hi, I want to see the calculation and result of a recursive method for calculating the complexity of recursive algorithm something like:if n = 1 then T(n) = 10else T(n) = 5T(n/2)The result should be a function of n (something like 3n + 20)How do I do that in Mathematica desktop document?Ilan
5 Replies
Sort By:
Posted 6 months ago
 RSolve will do this rather directly. RSolve[{t[1] == 10, t[2 n] == 5*t[n]}, t[n], n] (* Out[49]= {{t[n] -> 2 5^(1 + Log[n]/Log[2])}} *) 
Posted 6 months ago
 Suppose I will not use it RSolve to solve and then I have:  t[1] = 10; t[n_] := t[n] = 1/5*t[2*n] t[2] (* Error -> {10, Hold[t[2] = 1/5 t[2 2]]} *) How to get value for n=2 ?
Posted 6 months ago
 Interesting that RSolve does give a result, because there are only terms defined with arguments n=2^k. E.g. what could t[3] possibly be?
 t[3] should be 5*t/3/2] (and it is).This is not different from the following scenario. In[130]:= rr = RSolveValue[{t[1] == 2, t[n + 1] == 2*t[n]}, t[n], n] (* Out[130]= 2^n *) In[131]:= (rr /. n -> 3/2) == (2*rr /. n -> 1/2) (* Out[131]= True *) That is to say, the recurrence might be satisfied on a larger domain than is implied by the equatins that define it.