How to get Omega (n)

Question

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

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

Answer 1

Teacher’s theorem is not even applied, so the inability to use it is not a significant limitation.

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

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

A reasonable assumption for the lower bound is that a (n)> = n! for n> 1. This is true for n = 1. Assume that this is true for n = k-1.

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

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

A reasonable assumption for the upper boundary has the form a (n) <= 2 (n!). This is true for the first few values, but it turned out to be a little inconvenient to prove the use of induction. Sometimes with inductive evidence it is better to prove something stronger. In this case, it is better to prove that a (n) 2 (n!), Or that a (n) <= 2 (n!) - 1. This is true for n = 1. Assume that this 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!).

Answer 2

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

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

If so, then all O , Θ and Ω are equal to n! .

I believe that you can prove the above inequality or its variant using induction (although you have not tried it).

Answer 3

Hint:

Dividing a (n) by n !, the first terms have the form

 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 sets up hard bracketing.

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

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