Index
Introduzione
Questo metodo si basa sulla sostituzione dell’algoritmo ricorsivo con un algoritmo iterativo equivalente su cui effettuare l’analisi della complessità temporale.
Metodo
Il metodo iterativo per risolvere un’equazione di ricorrenza implica l’espansione delle chiamate ricorsive fino a raggiungere un caso base noto. Questo può aiutare a identificare un pattern che può essere utilizzato per formulare una soluzione generale.
Il metodo può essere semplificato in tre fasi:
- Espansione l’equazione di ricorrenza
- Osservazione del pattern
- Formula una soluzione generale Iterativa
- Calcolare costo asintotico
Nota
Solitamente basta espandere l’equazione di ricorrenza per 3 iterazioni per poter notare un pattern