Thread: average time for recursive algorithm

i think that this is the equation
Τ(n) = 1+T(i) + T(n-1-i)
i ε [ο,n], and i e IN (i is random)

and....the algorithm is

int function (int n){
int (n<=0) return 0;

else {
i = random(n-1);
return function(i)+function(n-1-i);

}
i have some ideas but..i am not sure
well???

ps random(int n) needs 1 time unit to give us a random integer value in [0,n]

Originally Posted by antonis_math

i think that this is the equation
Τ(n) = 1+T(i) + T(n-1-i)
i ε [ο,n], and i e IN (i is random)

and....the algorithm is

int function (int n){
int (n<=0) return 0;

else {
i = random(n-1);
return function(i)+function(n-1-i);

}
i have some ideas but..i am not sure
well???

ps random(int n) needs 1 time unit to give us a random integer value in [0,n]

Roughly speaking we should expect the average running time to be roughtly linear in n (as at each recursion we replace a computation of f(n) by two computations of something like f(n/2)).

Experiment bears this out.

This could be improved by writting a recursion formula for the expected running time for n=k in terms of the expected running times for n=0, 1, ..., k-1.

To me the recursion looks something like (but don't expect this to be exactly right, it needs checking):

t(k)=1+(2/k)[t(0)+t(1)+.. + t(k-1)]

where t(k) is the expected running time when n=k.

i think that the answer is n.
n can verify the equation.
proof by induction:...

edit: I wrote the message before I got your answer!

Originally Posted by Constatine11

Roughly speaking we should expect the average running time to be roughtly linear in n (as at each recursion we replace a computation of f(n) by two computations of something like f(n/2)).

Experiment bears this out.

This could be improved by writting a recursion formula for the expected running time for n=k in terms of the expected running times for n=0, 1, ..., k-1.

To me the recursion looks something like (but don't expect this to be exactly right, it needs checking):

t(k)=1+(2/k)[t(0)+t(1)+.. + t(k-1)]

where t(k) is the expected running time when n=k.

If the recursion is right, then as t(0)=0 we have t(k)=k satisfies the recursion and so is the solution.