Complessità, induzione e ricorrenze

In questa lezione abbiamo affrontato i principali metodi di risoluzione delle serie e delle equazioni alle ricorrenze che si trovano nell'analisi di complessità degli algoritmi.

Oltre alla risoluzione delle serie aritmetiche e geometriche, abbiamo visto tre metodi di risoluzione di impiego generale:

• Induzione
• Metodi di shifting
• Teorema maestro

Una dispensa che copre gli argomenti trattati in questa lezione si trova sul sito del corso di Algoritmi e Strutture Dati.