1. **Énoncé du problème :** Trouver l'élément majoritaire dans un tableau d'entiers naturels $T$ de taille $n$, c'est-à-dire un élément apparaissant strictement plus de $\frac{n}{2}$ fois. Si aucun élément ne satisfait cette condition, retourner $-1$. 2. **Stratégie Diviser pour Régner (Question a) :** - Diviser le tableau en deux moitiés. - Trouver récursivement l'élément majoritaire dans chaque moitié. - Si les deux moitiés ont le même élément majoritaire, c'est l'élément majoritaire du tableau entier. - Sinon, compter la fréquence de chaque candidat dans le tableau entier. - Retourner l'élément qui apparaît plus de $\frac{n}{2}$ fois, sinon $-1$. 3. **Relation de récurrence (Question b) :** La fonction divise le problème en deux sous-problèmes de taille $\frac{n}{2}$ et effectue un comptage en $O(n)$. $$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$$ 4. **Application du théorème du maître (Question c) :** Ici, $a=2$, $b=2$, et $f(n) = O(n)$. - Calcul de $\log_b a = \log_2 2 = 1$. - Puisque $f(n) = \Theta(n^{\log_b a})$, la complexité est $$T(n) = \Theta(n \log n)$$ 5. **Fonction itérative pour tableau trié (Question d) :** - Parcourir le tableau en comptant la fréquence consécutive de chaque élément. - Si la fréquence dépasse $\frac{n}{2}$, retourner cet élément. - Sinon, retourner $-1$. - Cette méthode est en $O(n)$ car chaque élément est visité une fois. **Réponse finale :** - Fonction diviser pour régner avec complexité $\Theta(n \log n)$. - Fonction itérative pour tableau trié avec complexité $O(n)$.