\begin{questions}
\item Voici un exemple d'algorithme en pseudo-code qui détermine la deuxième plus petite valeur de $T$.

\begin{algorithme}{}
Entrée: un tableau $T$ de $n$ entiers $(n \geqslant 2)$
Sortie: la deuxième plus petite valeur du tableau $T$
min1 $\leftarrow+\infty$
min2 $\leftarrow+\infty$
Pour i allant de 0 à n-1 :
     Si T[i] $<$ min1 alors
         min2 $\leftarrow$ min1
         min1 $\leftarrow$ T[i]
     Sinon si T[i] $<$ min2 alors
         min2 $\leftarrow$ T[i]
Fin du Pour
Afficher "La deuxième plus petite valeur est", min2
\end{algorithme}

\item L'algorithme effectue une unique boucle sur les $n$ éléments du tableau. À chaque itération, un nombre constant de comparaisons et affectations est réalisé. Le coût total de l'algorithme est donc \textit{linéaire}, soit de l'ordre de $O(n)$.

\item Voici un algorithme qui affiche également l'indice de la deuxième plus petite valeur.

\begin{algorithme}{}
Entrée: un tableau $T$ de $n$ entiers $(n \geqslant 2)$
Sortie: la deuxième plus petite valeur du tableau $T$
        et son indice

min1 $\leftarrow+\infty$, ind1 $\leftarrow$ -1
min2 $\leftarrow+\infty$, ind2 $\leftarrow$ -1
Pour i allant de 0 à n-1 :
     Si T[i] $<$ min1 alors
         min2 $\leftarrow$ min1
         ind2 $\leftarrow$ ind1
         min1 $\leftarrow$ T[i]
         ind1 $\leftarrow$ i
     Sinon si T[i] $<$ min2 alors
        min2 $\leftarrow$ T[i]
        ind2 $\leftarrow$ i
Fin du Pour
Afficher "La deuxième plus petite valeur est", min2,
"à l'indice", ind2
\end{algorithme}

\Par

Cet algorithme conserve le même coût linéaire $O(n)$.
\end{questions}
