This question already has an answer here:
I'm trying to prove that the following recurrence relation has a runtime of
fac(0) = 1 fac(n+1) = (n + 1) * fac(n)
I think that I can use induction in the following manner:
fac(n) = fac(0) = 1
fac(n) has a runtime of
fac(n+1) = (n + 1) * fac(n)
fac(n+1) has a runtime of
However, I have a suspicion that my inductive case doesn't really prove much. Maybe this is because the my assumption for the inductive case is wrong?
Can you point me in the right direction to prove this runtime?