Ordine asintotico

[Fede5...]

Ciao ragazzi, qualcuno saprebbe aiutarmi con il seguente esercizio?

Siano date le relazioni di ricorrenza

$ { ( H(n)=W(n/2) ),( W(n)=2H(n/4)+Theta (1) ):} $

con $ H(1)=Theta (1), W(1)=Theta(1) $ . Trovare l'ordine asintotico di A(n)=H(n)*W(n).

Grazie mille!!

[apatriarca]

Il metodo classico per risolvere questo tipo di equazioni di ricorrenza consiste nel fare una sostituzione in modo da ottenere due equazioni di ricorrenza con una sola funzione. Nel tuo caso hai quindi
\[
\begin{cases}
H(n) = W\big(\frac{n}{2}\big) = 2H\big(\frac{n}{8}\big) + \Theta(1) \\
W(n) = 2H\big(\frac{n}{4}\big) + \Theta(1) = 2W\big(\frac{n}{8}\big) + \Theta(1)
\end{cases}
\]

Le due funzioni rispettano insomma la stessa equazione di ricorrenza. Per quanto riguarda il prodotto hai che la complessità asintotica è moltiplicativa (devi insomma risolvere l'equazione di ricorrenza e prenderne il quadrato per \(A(n)\)).

[Fede5...]

Grazie mille,
quindi per trovare l'ordine asintotico di A(n) risolvo l'equazione di ricorrenza con il master theorem, dove trovandomi nel 2 caso ottengo che W(n) è $ Theta (0) $ (?)

[apatriarca]

Ti trovi nel primo caso, non nel secondo. Se \(c_{crit} = \log_8\,2 = 1/3,\) hai infatti che \(O(1) = O(n^0)\) e \(0 < 1/3\). Il risultato in questo caso è dato da \(\Theta(n^{c_{crit}}) = \Theta(\sqrt[3]{n})\).