Dubbio Equazione Di Ricorrenza

Dubbio Equazione Di Ricorrenza

Questo esercizio proposto da Roberti mi risulta O(N^4) invece che O(N^3), qualcuno riesce a risolverlo?
Grazie
Schermata 2020-01-06 alle 19.13.13

1 Mi Piace

usando il master theorem viene così.

photo_2020-01-07_17-17-37

1 Mi Piace

Qua è una risposta da terzo anno… Noi non abbiamo ancora affrontato le equazioni di ricorrenza in questo modo. Utilizziamo il metodo iterativo, quindi non possiamo utilizzare il metodo proposto da te

1 Mi Piace

Da secondo anno, intendi l analisi per livelli di iterazione? perdonami ma non ho idea di quale sia la teoria di prog 1 con Riccardi :sweat_smile:

Ecco la soluzione con il metodo che abbiamo visto durante il corso:
immagine

1 Mi Piace

Per ricavare T(\frac{n}{2}) non bisognerebbe sostituire N con (\frac{N}{2}) nella prima equazione?
Perchè cosi a me risulterebbe T(\frac{n}{2}) = 2T[(n/2)/2] + (n/2)^3
che sostituito in T(n) dà T(n)= 2(2T[(n/2)/2] + (n/2)^3 )+ n^3
e quindi T(n) = 2^i T(n/2^i) + 3^n + ‚ąĎ 2^i (n/2^i)^3