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)