exercice 2

Pour function_1: Les deux paramètres d'entrées sont des tableaux. On pose n et m les tailles respectives des tableaux tableau1 et tableau2. On a une boucle imbriqué dans une autre en fonction de la longueur des tableaux. La condition d'arrêt de la boucle sur tableau2 est vérifiée si un élément de tableau 2 est le même que l'élément ciblé dans tableau1. Ici, on calcule la complexité dans le pire des cas, c'est à dire qu'il n'y aucune intersection entre tableau1 et tableau2. On a une affection au début de la fonction, ce qui compte pour 1, et un test dans une boucle imbriquée. En considérant que la comparaison compte pour 1, on a la complexité suivante : nm+1 Ce qui revient à dire une complexité O(nm).

Pour function_2: on a un while en fonction du paramètre d'entrée (n). La condition qu'il vérifie est qu'il doit être strictement supérieur à 0, et il est décrémenté de 1 à chaque tour de boucle. On a donc une complexité linéaire: O(n).

Pour function_3: Aucune boucle dans cette fonction. Le nombre d'expressions exécutées ne dépend pas du paramètre. La complexité est donc de O(1).