How to get Omega(n)

问题:

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

回答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!).

回答2:

You have already noticed that your formula is very close to the factorial n!. Now you can express this finding in a more formal way: you can prove, for example, that

n! < a(n) < 2*n! (for big enough n)

If this is true, then all of O, Θ and Ω are n!.

I believe you can prove the inequality above, or some variant of it, using induction (haven't tried it though).

回答3:

Hint:

Dividing a(n) by n!, the first terms are

a(1)/1! = 1/1! = 1
a(2)/2! = (2.1+1)/2! = 1 + 1/2!
a(3)/3! = (3.(2.1+1)+1)/3! = 1 + 1/2! + 1/3!
a(4)/4! = (4.(3.(2.1+1)+1)+1)/4!= 1 + 1/2! + 1/3! + 1/4!
...

This establishes the tight bracketing

n! <= a(n) < (e-1).n!

and a(n) is in Θ(n!).