Using induction to prove a big O notation

Problem Detail: 

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 case

If n=0 then fac(n) = fac(0) = 1

Inductive case

Assume 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?

Asked By : Todd Davies

Answered By : shebang

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 definition

T(n) <= cn for all n >= n0 

Assume:

T(n - 1) <= c(n - 1) 

then

T(n) = T(n - 1) + O(1) T(n) <= c(n - 1) + d T(n) <= cn + d - c T(n) <= cn for c >= d 

use T(1) as a base case to complete the proof, giving you n0 = 1

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26084