CODEWITHSUNDEEP
algorithmrecursionrecurrence
Sam I Am
Sam I Am

Reputation: 13

determining recurrence relation for number of multiplications of an algorithm

I have an algorithm 

R(N)
{
    if(n<=2) return n;
    else
        sum=0;
        for i=1 to n-2
             sum+=(n-1)*R(i)
     return sum;
}

I want to get the recurrence for number of multiplications operations performed by R(n). if

T(n)=0 for n<=2

what is T(n) for n>2?

In addition, how can I show an exponential lower bound on complexity of M(n)?

Upvotes: 0

Views: 650

Answers (1)

kraskevich
kraskevich

Reputation: 18556

1) For n > 2:
T(n) = sum(f(i) + 1 for i from 1 to n - 2) = n - 2 + sum(f(i) for i from 1 to n - 2) The first equation is correct because
R(1), R(2), ..., R(n - 2) are called recursively and than one more multiplication is performed after each call.

2)The proof for exponential lower bound:

a) Let's assume that g(i) is such a sequence that:
g(0) = 0
g(1) = 1
g(2) = 1
g(3) = 1
g(i) = g(i - 2) + g(i - 3) for i >= 4
Then g(i) <= R(i + 3) for any valid i, because a formula for g(i) is obtained by removing n - 2 and g(1), g(2),...,g(i - 4) from the right side of the recursive formula for R(and all terms are non-negative).

b) On the other hand, g(i) >= f(i / 2), where f(i) is a Fibonacci sequence (here I assume that f(0) = 0, f(1) = 1, f(2) = 1 and so on).
Proof:
1) Base case: for i <= 4 this inequality holds true(one can simply check it).
2) Induction: g(i) = g(i - 2) + g(i - 3) >= f((i - 2) / 2) + f((i - 3) / 2) >= f(i / 2 - 1) + f(i / 2 - 2) = f(i / 2).

c) Thus, f(i) <= g(i) <= R(i + 3) so R is lower bounded by Fibonacci sequence. And Fibonacci sequence grows exponentially!

Upvotes: 1

Related Questions