Come ottenere Omega (n)

Question

Ho la formula a (n) = n * a (n-1) +1; un (0) = 0

Come posso ottenere l'Omega, Theta o notazione O da questo senza il teorema o Qualcuno avere un buon sito per comprendere la spiegazione

Answer 1

Il teorema di Master non si applica nemmeno, quindi non essere in grado di usarlo non è una grande limitazione.

Un approccio che funziona qui è di indovinare limiti superiori e inferiori, e quindi provare queste ipotesi per induzione se le ipotesi sono buone.

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

una ragionevole ipotesi di un limite inferiore è che una (n)> = n! per n> 1. Questo è vero per n = 1. Supponiamo che sia vero per n = k-1.

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

Quindi, se è vero per n = k-1, allora è vero per n = k, quindi una (n)> = n! per tutti gli interi positivi n e a (n) = Omega (n!).

Un'ipotesi ragionevole per un limite superiore è a (n) < = 2 (n!). Questo è vero per i primi valori, ma risulta essere un po 'scomodo provare l'uso dell'induzione. A volte con prove induttive, è meglio provare qualcosa di più forte. In questo caso, è meglio dimostrare che a (n) < 2 (n!) O che a (n) < = 2 (n!) - 1. Questo è vero per n = 1. Supponiamo che sia vero per n = k-1 per alcuni k-1> = 1. Poi

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

Quindi, per ogni n> = 1, a (n) < 2 (n!). Dato che abbiamo un limite inferiore e un limite superiore della forma c * (n!), A (n) = Theta (n!).

Answer 2

Hai già notato che la vostra formula è molto vicino al fattoriale n!. Ora è possibile esprimere questo risultato in un modo più formale: si può dimostrare, per esempio, che

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

Se questo è vero, allora tutti i O, Θ e Ω sono n!.

Credo che si possa provare la disuguaglianza di cui sopra, o qualche variante di essa, usando l'induzione (non l'ho provata però).

Answer 3

suggerimento:

Divisione di un (n) per n !, i primi termini sono

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! 
... 

Questo stabilisce la staffaggio stretto

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

e a(n) è in Θ(n!).