Recurrence relation on Factorial

Question

I was studying recurrence by a slide found at (slide 7 and 8):

http://www.cs.ucf.edu/courses/cop3502h/spring2012/Lectures/Lec8_RecurrenceRelations.pdf

I just can't accept (probably I`m not seeing it right) that the recurrence equation of factorial is :

T(n) = T(n-1)+2
T(1) = 1

when considering the number of operations ("*" and "-") of the function :

int factorial(int n) {
 if (n == 1)
 return 1;
 return n * factorial(n-1);
}

If we use n = 5 we will get 6 by the formula above while the real number of subs and molts are 8.

My teacher also told us that if analyzing only the number of "*" it would be :

T(n) = T(n-1)+1.

Again if I use n = 5, I would get 5 but if you do it on a paper you will get 4 multiplications.

I also checked on the forum, but this Question is more messed then a hell : Recurrence Relation

Anyone could help me understand that ? thanks.

Answer 1

if we use n = 5 we will get 6 by the formula above while the real number of subs and molts are 8.

It seems that the slides are counting the number of operations, not just subtractions and multiplications. In particular, the return statement is counted as one operation. (The slides say, "if it’s the base case just one operation to return.")

Thus, the real number of subtractions and multiplications is 8, but the number of operations is 9. If n is 5, then, unrolling the recursion, we get 1 + 2 + 2 + 2 + 2 = 9 operations, which looks right to me.