[Algoritmi] Dubbi Dimostrazioni complessità asintotica

[Grimr]

Salve, sto riscontrando delle difficoltà nel dimostrare la seguente affermazione (e in generale in tutte le dimostrazioni simili):

$ (n + 2)3^n = O((4^n)/n) $

Utilizzando la definizione lo scopo è trovare le due costanti $ c $ e $n_0$ per cui vale

$ (n+2)3^n <= (4^n)/n, AA n>=n_0$

Ma a questo punto non ho proprio idea di come procedere... scelgo la costante $c$ e trovo $n_0$? O viceversa? Grazie in anticipo per l’aiuto

[apatriarca]

Hai dimenticato di inserire la costante \(c\) nella tua diseguaglianza. In ogni caso tratti di solito la \(c\) come l'incognita e quando fai delle semplificazioni aggiungi delle condizioni su (n.\)

In particolare inizi riscrivendo la tua disuguaglianza in modo da estrarre \(c\). Hai quindi:
\[ c \geq \frac{n\,(n + 2)\,3^n}{4^n} \]
Per \(n > 1\) hai che \(n\,(n+2) < 4\,n^2.\) Portiamo poi i due esponenti alla stessa base in modo da poterci fare qualcosa. Puoi scrivere \(3^n = 2^{n\,\log 3}\) e \(4^n = 2^{2\,n}\) ottenendo
\[ c \geq 4\,n^2\,2^{n\,(\log 3 - 2)} \]
Hai che \(\log 3 - 2 < -0.4\) per cui \( e^{n\,(\log 3 - 2)} < e^{-n/3} \) per ad esempio \(n > 3\). Riscriviamo \( 4\,n^2 = 2^{ 2 + 2\,\log n } \) ottenendo infine:
\[ c \geq 2^{ 2 + 2\,\log n - n/3 } \]
A questo punto puoi scegliere un valore di \(c\) per cui questa disuguaglianza ha senso e usarlo per trovare un \(n\) che vada bene. Se per esempio scegli \(c = 4\) ottieni \(1 \geq 2^{2\,\log n - n/3} \) da cui prendendo il logaritmo hai \( n \geq 6\,\log n. \) Questo è certamente vero per \(n > 32.\) Nota che normalmente non sei interessato a sapere i valori più piccoli per cui questo è verificato. Devi solo dimostrare che esistono.

[Grimr]

Grazie mille davvero

[Grimr]

Per \(n > 1\) hai che \(n\,(n+2) < 4\,n^2.\) Portiamo poi i due esponenti alla stessa base in modo da poterci fare qualcosa.

Per lo stesso ragionamento al secondo passaggio avrebbe senso sostituire $ 3^n$ con $4^n$ per ottenere
$ c >= (n(n+2)4^n )/ 4^n $ ?

[apatriarca]

Quel passaggio porterebbe a eliminare i due esponenziali e a rimanere con una costante maggiore di una sequenza che tende all'infinito.