How to get Omega(n)

Question

I have the formula a(n) = n * a(n-1) +1 ; a(0) = 0

How can i get the Omega, Theta or O Notation from this without the Master Theorem or did anyone have a good site to understand the explanation

Answer 1

The Master theorem doesn't even apply, so not being able to use it isn't much of a restriction.

An approach which works here is to guess upper and lower bounds, and then prove these guesses by induction if the guesses are good.

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 10
a(4) = 41

A reasonable guess for a lower bound is that a(n) >= n! for n>1. This is true for n=1. Suppose it is true for n=k-1.

a(k) = ka(k-1)+1 
     >= k (k-1)! + 1 
     >= k!. 

So, if it is true for n=k-1, then it is true for n=k, so a(n) >= n! for all positive integers n, and a(n) = Omega(n!).

A reasonable guess for an upper bound is at a(n) <= 2(n!). This is true for the first few values, but it turns out to be a little awkward to prove using induction. Sometimes with inductive proofs, it is better to prove something stronger. In this case, it's better to prove that a(n) < 2(n!), or that a(n)<=2(n!)-1. This is true for n=1. Suppose it is true for n=k-1 for some k-1>=1. Then

a(k) = k(a(k-1))+1 
    <= k(2(k-1)!-1)+1 
     = 2(k!) +1-k 
    <= 2(k-1)!-1. 

So, for any n>=1, a(n) < 2(n!). Since we have a lower bound and an upper bound of the form c*(n!), a(n) = Theta(n!).