Equazione per ricorrenza

[Sk_Anonymous]

Discutere il comportamento asintotico della seguente funzione:

$T(n)=3T(n/4)+log(n)$ se $n>1$
$T(n)=1$ se $n=1$

Ho provato con l'albero delle chiamate ricorsive, ma mi perdo nelle sommatorie finali. Qualche suggerimento? A me interesserebbe trovare un $\Theta(f(n))$.

[adaBTTLS1]

forse non sarò in grado di aiutarti, ma mi sorge un dubbio che potrebbe essere importante chiarire, anche per l'intervento di altre persone: c'è per caso un simbolo di parte intera che dovevi utilizzare e che non si vede dalla formula? altrimenti, che cosa significa $T(n/4)$ se n non è multiplo di 4? ciao.

[TomSawyer1]

Ti è consentito usare il metodo dell'esperto?

[vict85]

"TomSawyer":Ti è consentito usare il metodo dell'esperto?

Effettivamente il problema sembra fatto apposta...

[Sk_Anonymous]

Non conosco quello che voi chiamate "metodo dell'esperto"

[vict85]

cercalo su internet... neanche io lo conoscevo, l'ho cercato su google e ho visto che si applica esattamente al tuo caso...

[Sk_Anonymous]

Non trovo nessun link googlando

[adaBTTLS1]

mi sono incuriosita ed ho cercato io... tra varie cose trovate, questa mi sembra la migliore... (ma forse non sono molto adatta a giudicare):

http://www.cs.unicam.it/merelli/algorit ... rrenze.pdf

ho visto che ci sono vari simboli che richiamano la parte intera, anche se mi pare con diversi significati...
ciao.