ESERCIZI VARI SU RICORRENZE (ASD)

[Giova411]

Volevo iniziare una "raccolta di ricorrenze".
Questo per non aprire ogni volta un Topic nuovo per ogni ricorrenza...
Iniziamo!
Mi sapreste aiutare con la seguente?

\(\ T (n) = 3T \sqrt(n) + log n \)

Ho provato a sostituire \( m = lg n \) per avere \( T(2^m) = 3 T(2^{1/2 m}) + m \)
poi ancora \( S(m) = T(2^m) \) non so se arrivo correttamente a \( S(m) = 3 S(m/2) + m \)
dopo questo, sempre se corretto, mi perdo....

[Giova411]

Grazie Tem, ma non credo sia giusto però

[Giova411]

Per quanto interessante non lo capisco bene quel sito


Partendo sempre dalle origini:
\(\ T (n) = 3T \sqrt(n) + log n \)
Secondo i miei calcoli potrebbe venire tipo:
\(\displaystyle T(n) \in \Theta( lg n^{lg 3} )\) ??

[hamming_burst]

dai un occhio a questo.

[Giova411]

"hamming_burst":dai un occhio a questo.

LO VEDI DOV'E' HAMMMING!!!!!! =)
Dov'eri finito?!?!?
Visto l'esempio!!! (dove cantavi e suonavi da solista )

Quindi suppongo sia giusto anche il mio esercizio

[Giova411]

Dopo la ricorrenza di cui sopra, che spero abbia un ordine di grandezza preciso/corretto , chiedo aiuto con questa:

\( \ T (n) = 4T (n/2) + n^2 log n \)

Col Master non si riesce poiché non trovo un Epsilon per cui "domino chiaramente al di sopra" e manco qualcosa che domina inferiormente...
Che supposizione posso fare per risolverlo? Non mi viene il cosidetto "sparare la GUESS"....