Originariamente inviato da YuYevon
Come hai impostato la relazione di ricorrenza? Hai usato il metodo dell'esperto (o "principale")? Se sì, in quale dei tre casi ti ritrovi? Dal risultato che hai scritto direi che hai verificato il primo... ma a me non sembra che siano soddisfatte le ipotesi di quest'ultimo...

la relazione di ricorrenza dovrebbe essere

F(N) = 1 se N<=1
e
F(N) = 2[F(N/3)] + N se N>1

direi piuttosto che siamo nel terzo caso del teorema e non nel primo.
la funzione di ricorrenza è quella lì...non so come si chiami il metodo(il prof nn ce l'ha detto) cmq ho iterato più volte la funzione di ricorrenza per N>1, fino a trovare una generalizzazione, che è la seguente:
F(n)=2^k *F(n/3^k) + sommatoria con i=1 fino a k di O(1)

A questo punto impongo la condizione d'uscita, che è: n=3^k. Adesso sosituisco a k=log inbase3 di n.
F(n)=2^(logbase3 di n)+ sommatoria con i=1 fino a logbase3 di n di O(1)
il tutto si riduce ad
2^(logbase3 di n) dato che la sommatoria è di O(1)...
Spero di farmi capire :S