Fondements de l'Analyse d'Algorithmes

Écrire une fonction récursive simple (ex: factorielle, Fibonacci) et tracer son arbre d'appels.

Définir et distinguer les notations asymptotiques O, Ω et Θ avec des exemples formels.

Calculer la complexité temporelle dans le pire des cas et la complexité spatiale d'un algorithme itératif.

Résoudre une récurrence simple par la méthode de substitution (ex: T(n) = T(n-1) + c).

Appliquer le théorème maître pour résoudre des récurrences de type diviser pour régner.

Comparer la complexité de deux algorithmes et justifier formellement lequel est plus efficace.