[Algoritmi] Chiarimenti su analisi asintotica della complessità

[Fra27]

Buonasera a tutti, non riesco a chiarire questo dubbio:
Per la risoluzione di un'equazione di ricorrenza come faccio a stabilire se ha ordine $O(g(n))$ o $Theta(g(n))$? Dal punto di vista teorico mi è chiaro il significato di entrambi, però quando guardo la risoluzione di alcuni esercizi non riesco a capire il ragionamento che è stato applicato.

Per definire che un algoritmo ha complessità $Theta(g(n))$ devo conoscere anche $\mathcal{Omega}(g(n))$, come faccio a trovarmi la limitazione inferiore? Grazie a chi risponderà!!

[Fra27]

Nessuno riesce ad aiutarmi?

[apatriarca]

La domanda è troppo generica. Stia in pratica chiedendo come calcolare la complessità di qualcosa e ci sono tantissimi modi diversi in cui questo si possa fare. Dipende dai casi. Esempi di metodi sono:
1. Trovare il caso migliore.
2. Dimostrare che la complessità non dipende dall'input.
3. Dimostrare che il tuo algoritmo ha una complessità uguale o peggiore di un altro algoritmo di cui conosci la complessità..
4. ...

C'è qualche esempio in particolare in cui hai difficoltà?

[Fra27]

C'è qualche esempio in particolare in cui hai difficoltà?

Allora noi abbiamo studiato 5 metodi per l'analisi della complessità di una relazione di ricorrenza:

1) Metodo Iterativo
2) Metodo di sostituzione
3) Metodo del cambio di variabile
4) Metodo dell'albero di ricorsione
5) Teorema Master delle ricorrenze

Allora ad esempio è possibile utilizzare il metodo iterativo per la seguente rel. di ricorrenza:
$T(1)=c$
$T(n)=T(n/2)+c$ $ se$ $ n>1$

La soluzione è$ Theta(log n) $

Mentre sempre con lo stesso metodo questa seconda relazione :
$ T(1)=2$
$T(n)=8* T(n/2)+n$ $ se$ $n>1 $

Ha soluzione è $O(n^3)$

Ho visto tutta la risoluzione ma non capisco perchè nel primo è nota la limitazione inferiore mentre nel secondo no.

[apatriarca]

Non ho capito come è fatta la seconda equazione di ricorrenza..

[Fra27]

Pardon, ora l'ho modificata.

[apatriarca]

In base al master theorem hai che \(\log_2 8 = 3\) e \( n \in O(n) \) per cui vale il primo caso e \( T(n) \in \Theta(n^3).\) Non c'è insomma nessuna differenza tra i due casi, a parte la scelta di porre l'attenzione solo sulla limitazione superiore invece che su entrambe. In ogni caso hai che \( f(n) \in \Theta(g(n)) \implies f(n) \in O(g(n))\). Spesso si è solo interessati al caso peggiore e quindi si usano relazioni meno precise. Ci sono tuttavia casi in cui una funzione è \(O(g(n))\) ma non \(\Theta(g(n))\).

[Fra27]

Ma la prima equazione è stata risolta con il metodo iterativo e non con il teorema master. Ecco il mio dubbio. Come faccio ,utilizzando un metodo che non sia il teorema master, a sapere la limitazione inferiore e quindi \( \Theta(g(n)) \) ?