Analysis of Recursive Algorithms

Question

So say I'm going to analyze a factorial function:

pseudocode:

F(n)
if n=0 return 1
else return f(n-1)*n

This is my basic operation: $F\left(n\:-\:1\right)\cdot n$

now when it comes to the recurrence relation which is:

$M\left(n\right)\:=\:M\left(n\:-\:1\right)\:+\:1$

I don't quite grasp where the $+\ 1$ is coming from or what it means. My lecture notes say that it means to multiply $F\left(n\:-\:1\right)$ by $n$, but this isn't very clear to me.

Answer 1

I assume that $M(n)$ is supposed to represent some formulation of the time it takes to run $F(n)$; in this case, imagine that $M(n) = M(n-1)$ instead of $M(n)$. Then $M(1000) = M(999) = M(998) = $ ... $ = M(0)$ (I'm also assuming that $M(0) = 1$), so the time required to run $M(1000)$ would equal to the time required to run $M(0)$. On the other hand, if $M(n) = M(n-1) + 1$, then $M(1000) = M(999) + 1 = M(998) + 2 = M(997) + 3 =$ ... $= M(0) + 1000$. Essentially, the +1 is indicating that there is a unit of time spent evaluating a single call of the function, which includes performing the multiplication of $F(n-1) \cdot n$ and evaluation of the if-statement.