Calculate the complexity of a recursive algorithm?

Questions
1

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) = 10
else 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

2

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])}} *)
3

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 ?

4

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?

5

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.

6

Thank you all. Actually I did not meant that the coefficients will matter I gave just because I did not want you to be confused with letters as coefficients.
Any way I learned a lot from the answers because I am new to Mathematica.
Ilan Hindy