Results 1 to 4 of 4

Math Help - average time for recursive algorithm

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    2

    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]
    Last edited by antonis_math; December 24th 2008 at 03:24 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by antonis_math View Post
    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.
    Last edited by Constatine11; December 24th 2008 at 04:47 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    Posts
    2
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by Constatine11 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 17th 2009, 02:53 PM
  2. Recursive Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 6th 2009, 02:55 AM
  3. Recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 10th 2008, 11:44 PM
  4. Recursive Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2008, 11:56 PM
  5. Recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2008, 05:50 AM

Search Tags


/mathhelpforum @mathhelpforum