Ah ok, quindi non conoscete il metodo dell'esperto... è un teorema (ovviamente con una signora dimostrazione) che ti consente di risolvere alcune relazioni di ricorrenza semplicemente verificando delle ipotesi iniziali. Vabbè comunque leggo che hai usato il metodo iterativo - sul quale non sono molto pratico, quindi correggimi se sbaglio - però provando a sviluppare i calcoli non mi trovo esattamente con te quando dici

F(n)=2^k *F(n/3^k) + sommatoria con i=1 fino a k di O(1)
non mi trovo con la parte in rosso (quella prima va bene). Provo a postare dei calcoli:

F(n) = 2[F(n/3)] + n

calcoliamo F(N/3):

F(n/3) = 2[F(n/9)] + n/3

quindi F(n) diventa

F(n) = 2{2[F(n/9)] + n/3]} + n

alias

F(n) = 4[F(n/9)] + (2/3)n + n

ora, calcolando ancora F(n/9) abbiamo:

F(n/9) = 2[F(n/27)] + n/9

per cui F(N) diventa

F(n) = 4{2[F(n/27)] + n/9} + (2/3)n + n

che, facendo i calcoli, è

F(n) = 8[F(n/27)] + (4/9)n + (2/3)n + n

praticamente hai dimenticato i termini con n...

se continuassimo avremmo in sostanza che quei termini con n sono:

... (16/81)n (8/27)n + (4/9)n + (2/3)n + n

quindi i coefficienti sono un rapporto tra potenze di 2 (sopra) e di 3 (sotto), con esponenti uguali (0, 1, 2, 3...)

mettiamoli in evidenza. Abbiamo

n(16/81 + 8/27 + 4/9 + 2/3 + 1)

cioè n per sommatoria per i che va da 0 a k di 2^i / 3^i

la generalizzazione - secondo questi calcoli - è

F(N) = 2^k [F(n/3^k)] (e ci siamo) + n*"sommatoria i=0,...,k-1 di 2^i / 3^i"

a questo punto non ho continuato ma ricordando che



forse dovresti riuscire a venirne fuori...

NB: quella serie che ho ricavato va da 0 a k-1, infatti se k (ad esempio) è 2, tu hai

F(n) = 4[F(n/9)] + (2/3)n + n, e cioè

F(n) = 2^k[F(n/3^k)] + n(2/3)^(k-1) + n(2/3)^(k-2)

dove quindi k-1 vale 1 ( e infatti hai 2/3 elevato a 1 ) e k-2 vale 0 ( e infatti 2/3 elevato a 0 fa 1, e cioè il coefficiente dell'ultima n )