[Algoritmi] Relazioni di ricorrenza

[Lotharis]

Buongiorno,
Sono uno studente del secondo anno di informatica.
Durante lo svolgimento di alcuni esercizi mi sono imbattuto nel seguente:
$ T(n) = pT(n/2)+n^3log_3n+n^4 $
$ T(1) = 1 $
dove p è un intero positivo. Si dica, giustificando le risposte, se
per opportuni valori di p è possibile che sia:
1) $ T(n) = Theta (n^4) $
2) $ T(n) = Theta (n^5) $
3) $ T(n) = Theta (n^2) $
Ci ho provato in vari modi ma non ne sono ancora venuto a capo.
Grazie in anticipo.

[apatriarca]

Ciao, benvenuto nel forum.

Il problema mi sembra pensato per applicare il master theorem. Sia \(c_{crit} = \log_2 p\) e inizia a scrivere \(f(n) = n^3\,\log_3\,n + n^4 = \Theta(n^4).\) A questo punto hai i seguenti 3 casi del master theorem:

1. Se \(c_{crit} > 4\) (e quindi \(p > 2^4 = 16\)) hai che \(T(n) = \Theta(n^{c_{crit}})\). Puoi quindi certamente avere \(4 < c_{crit} = 5\) con \(p = 32\). Puoi quindi ottenere la seconda complessità del quesito.

2. Il secondo caso vale quando \(f(n) = \Theta(n^4) = \Theta(n^{c_{crit}}\,\log^{k}\,n)\) per un qualche \(k \ge 0\). E' certamente vero per \(p = 16\) e \(k = 0\). Tuttavia in questo caso avresti che \(T(n) = \Theta(n^4\,\log\,n)\) che non appartiene a nessuna delle soluzioni proposte.

3. Nel terzo caso consideri \(c_{crit} < 4\). In questo caso hai bisogno della condizione aggiuntiva \(p\,f(n/2) \le k\,f(n)\) per \(n\) sufficientemente grande e \(k \leq 1\). Non mi sembra ci siano problemi a verificare la condizione aggiuntiva e in questo caso hai che \(T(n) = \Theta(f(n)) = \Theta(n^4)\). Ti trovi quindi nella prima soluzione del tuo problema. In questo caso hai quindi \(p < 16\).

L'ultima soluzione non è chiaramente ottenibile in quanto \(f(n)\) rappresenta un limite sotto il quale non puoi andare con la complessità.

[Lotharis]

Grazie mille per la risposta .
Mi sono accorto solo ora che, a causa di una mia svista nello scrivere la prima ricorrenza, ho inserito $ T(n/2) $ invece che $ T(n/3) $ .
Il ragionamento dietro la soluzione è simile a quello precedente?
Devo porre $ c_(crit) = log_3p $ e scrivere anche in questo caso $ f(n) = n^3log_3n + n^4 = Theta(n^4) $?

[apatriarca]

Cambiano i numeri, ma non il ragionamento.