Recurrence Equation for new Algorithm of Factorial

Question

I am looking for a recursive algorithm to evaluate what I call Factorial(m,n)=m*m+1*...*n, for every m

I appreciate any help.

What is the complexity of this algorithm?

Answer 1

Let T(n, m) be the time complexity of Factorial(n, m).

Let g(n) = Factorial(n, 1) and T"(n) be the time complexity of g(n), then:

T(n, m) <= T"(n) + T"(m - 1) for any n, m

and T"(n) = T"(n - 1) + O(1) which is O(n).

To sum up, T(n, m) = O(n) + O(m - 1) = O(n + m)