[Examen Blanc] Tâche 1 : Meilleur et pire cas

On souhaite trier une liste d'entiers. L'algorithme proposé est le suivant:

Etape 1 : créer un arbre binaire de recherche T vide

Etape 2 : insérer les n éléments de la liste, 1 par 1, dans T

Etape 3 : faire un parcours infixe de T pour récupérer la liste ordonnée

Paste this command into your terminal:

The password to connect is

Please answer to all the questions. Internal error {} has not a valid extension. {} is too heavy.

Question 1: Complexité temporelle de l'étape 1

Déterminez la complexité temporelle de l'étape 1. On vous demande d'identifier la borne la plus appropriée.

\(\Theta(n^2)\)

\(O(n^2)\)

\(\Theta(\log(n))\)

\(O(0)\)

\(\Theta(n)\)

\(\Theta(1)\)

\(O(n)\)

\(O(\log(n))\)

Question 2: Complexité temporelle de l'étape 2

Déterminez la complexité temporelle de l'étape 2. On vous demande d'identifier la borne la plus appropriée.

Attention : bien que les n éléments de T soient ajoutés un par un, on s'intéresse ici à la complexité globale, c'est-à-dire à la complexité de l'ajout des n éléments.

\(\Theta(1)\)

\(O(n^2)\)

\(\Theta(n)\)

\(\Theta(n^2)\)

\(O(n)\)

\(\Theta(n \log(n))\)

\(\Theta(\log(n))\)

\(O(\log(n))\)

\(O(n \log(n))\)

Question 3: Complexité temporelle de l'étape 3

Déterminez la complexité temporelle de l'étape 3. On vous demande d'identifier la borne la plus appropriée.

\(O(\log(n))\)

\(\Theta(1)\)

\(\Theta(n \log(n))\)

\(\Theta(n^2)\)

\(\Theta(n)\)

\(\Theta(\log(n))\)

\(O(n)\)

\(O(n^2)\)

\(O(n \log(n))\)

Question 5: Identification de pire cas

Sélectionnez, parmi les propositions suivantes, l(es) instance(s) qui correspond(ent) à un pire cas pour la complexité temporelle de l'algorithme proposé.

Author(s)	Pierre Dupont
Deadline	01/09/2026 16:00:00
Submission limit	No limitation

Information

Sign in

Question 1: Complexité temporelle de l'étape 1

Question 2: Complexité temporelle de l'étape 2

Question 3: Complexité temporelle de l'étape 3

Question 4: Complexité temporelle de l'algorithme

Question 5: Identification de pire cas

Information

Sign in