I'm trying to prove that the following recurrence relation has a runtime of O(n): fac(0)   = 1 fac(n+1) = (n + 1) * fac(n)I think that I can use induction in the following manner:Base caseIf n=0 then fac(n) = fac(0) = 1Inductive caseAssume that fac(n) has a runtime of O(n)fac(n+1) = (n + 1) * fac(n)Therefore fac(n+1) has a runtime of O(n+1)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?
Using induction to prove a big O notation
complexity theory;asymptotics
In essence, your proof is correct. A more general solution that you can use for recursive algorithms is this.The way to solve this is to create a function T(n) that measures the runtime of the function and figure out the big O notation for it.To solve a problem of size n, I must solve a problem of size n - 1. Then I must perform constant time arithmetic to get the answer. Thus :T(n) = T(n - 1) + O(1)Prove T(n) is O(n) ie by definitionT(n) <= cn for all n >= n0Assume:T(n - 1) <= c(n - 1)thenT(n) = T(n - 1) + O(1)T(n) <= c(n - 1) + dT(n) <= cn + d - cT(n) <= cn for c >= duse T(1) as a base case to complete the proof, giving you n0 = 1