Matematicamente.it

Salve ragazzi, sto studiando le ricorrenze ed ho dei dubbi riguardo 2 metodi:albero di ricorsione e sostituzione.
Ho questa ricorrenza:
$T(n)={ ( 1 ),( T(n/2)+2T(n/4)+n ):}$ Primo caso se n=0,1 Secondo caso n>1.
Se sviluppo l'albero mi ritrovo per ogni livello $3^i$ nodi, però ad esempio per il livello 1, ho 2 nodi che sono $cn/4$ ed uno $cn/2$, quindi non so come gestire questa situazione per calcolare poi i livelli di tale albero e quindi ipotizzare una soluzione per utilizzare il metodo di sostituzione.
Inoltre ho un'altra domanda per il metodo iterativo nel caso, come questo, ci siano 2 o più chiamate interne, vanno sviluppate separatamente in modo da calcolarsi il limite inferiore e superiore?

Non mi sembra un esercizio banale, l'unica cosa che si vede e' questa:

$T(n) = $

$T(n/2)+ T(n/4) + n$
e adesso scompongo solo $T(n/2)$

$2T(n/4) +T(n/8) + n + n/2$
e qui scompongo solo $T(n/4)$

$3T(n/8) +2T(n/16) + n + n/2 + 2n/4$

$5T(n/16) +3T(n/32) + n + n/2 + 2n/4 + 3n/8$

$Fib(log(n)) + kn $

A sinistra si vede la sequenza di Fibonacci, a destra c'e' qualcosa che non cresce molto rapidamente.
Secondo me oltre a questo risultato non si va.
Come dici tu non vengono date informazioni su cosa fare con termini come $T(k), k<1$, ad es $T(1/2)$.
Si puo' supporre di considerarli tutti uguali a 1.

Quinzio ha scritto:Non mi sembra un esercizio banale, l'unica cosa che si vede e' questa:

$T(n) = $

$T(n/2)+ T(n/4) + n$
e adesso scompongo solo $T(n/2)$

$2T(n/4) +T(n/8) + n + n/2$
e qui scompongo solo $T(n/4)$

$3T(n/8) +2T(n/16) + n + n/2 + 2n/4$

$5T(n/16) +3T(n/32) + n + n/2 + 2n/4 + 3n/8$

$Fib(log(n)) + kn $

A sinistra si vede la sequenza di Fibonacci, a destra c'e' qualcosa che non cresce molto rapidamente.
Secondo me oltre a questo risultato non si va.
Come dici tu non vengono date informazioni su cosa fare con termini come $T(k), k<1$, ad es $T(1/2)$.
Si puo' supporre di considerarli tutti uguali a 1.

Scusami avevo sbagliato il testo, il secondo T aveva un 2 che lo moltiplicava, modifico.

Quindi su l'albero di ricorsione non ci sono strade per calcolare il numero di livelli, il generico sottoproblema al livello iesimo e via dicendo?