Message Boards Message Boards

0
|
4926 Views
|
5 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Calculate the complexity of a recursive algorithm?

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
POSTED BY: Ilan Hindy
5 Replies
Sort By:

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
POSTED BY: Ilan Hindy

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 BY: Daniel Lichtblau

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 BY: Mariusz Iwaniuk

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?
POSTED BY: Henrik Schachner

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.
POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract