====== 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'[[wp>Run-time_analysis|analisi di complessità]] degli algoritmi.

Oltre alla risoluzione delle serie aritmetiche e geometriche, abbiamo visto tre metodi di risoluzione di impiego generale:
  * [[wp>Mathematical_induction|Induzione]]
  * Metodi di shifting
  * [[wp>Master_theorem|Teorema maestro]]

Una [[http://home.dei.polimi.it/pradella/ASD/dispensaInfo3.pdf|dispensa]] che copre gli argomenti trattati in questa lezione si trova sul sito del corso di [[http://home.dei.polimi.it/pradella/ASD|Algoritmi e Strutture Dati]].