Hugo Raban et Patrick Felix-Vimalaratnam

Ex 2

Code 1

La complexité de ce code est de O(n*m) car pour chaque valeur du tableau1 on va regarder toutes les valeurs du tableau2.

Code 2

La complexité de ce code est de O(n) car le nombre d'itération de la boucle dépend de la valeur de x.

Code 3

La complexité de ce code est de O(1) car peu importe la valeur de x, il n'y a pas de boucle.

Ex 3

Le code trie récursivement chaque sous-tableau, puis trie le tableau courant selon la somme des sous-tableaux.

À chaque niveau, le tri coûte O(M*log(⁡M)) et chaque comparaison parcourt tous les éléments du sous-tableau (O(M^(n−1))).

Donc pour un tableau à N dimensions et M éléments par niveau, la complexité totale est O(M^N*log(⁡M)).