[Algo] Esercizio notazione asintotica

[Pablitos23]

Dimostrare che:

$f(n) = 4n + logn + 2 in theta n $

- Quindi calcolo prima la parte dell' $Omega$:

$c_1 n <= 4n + logn + 2$ Il mio ragionamento è il seguente:

procedo esplicitando la $c_1$

$c_1 <= 4 + logn/n + 2/n$

Ora penso: la mia c1 dovrà essere uguale al minimo valore che può assumere il membro di destra e quindi sarà:

$c_1 = 4$

- Procedo col calcolo dell' $O$:

$ 4n + logn + 2 <= c_2n$ come prima esplicito $c_2$

$ 4 + logn/n + 2/n <= c_2$

Ora il ragionamento è il seguente: la mia c2 dovrà essere uguale al massimo valore che può assumere il membro di destra e quindi $c_2 = 6$

La mia soluzione è che $f(n) in theta n$ con $c_1 = 4$, $c_2= 6$, $AAn > 0$


Però la soluzione della prof è $c_1 = 4$, $c_2 = 5$, $AAn>4$.
E' più precisa la sua ma la mia potrebbe andare??

[giuspeppe94]

Certo che è giusta anche la tua. Tu dai una stima dall'alto di 6n, e siccome 5n va bene definitivamente, a maggior ragione va bene anche 6n.

[Pablitos23]

Però la mia stima è più lasca e per algoritmi più complessi potrebbe esser meglio trovare due funzioni che approssimano meglio l'intervallo dell'andamento della funzione anche da un certo input in poi.
Ti ringrazio per la risposta.

[apatriarca]

Quelle costanti non sono particolarmente importanti, l'analisi asintotica della complessità è comunque pur sempre una approssimazione e semplificazione di quello che realmente succede. Non è effettivamente in grado di stimare le reali performance di un algoritmo su un computer reale. Queste performance possono infatti dipendere anche da molti fattori non presenti nel tuo modello (per esempio non si tiene spesso conto della memoria).

[Pablitos23]

Capito e grazie