questao_8.tex

\begin{center}
    \begin{tabular}{cccccccccc}
      10 & 9 & 8 & 7 & 6 & 5 & 4 & 3& 2 & 1* \\
      1 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3& 2*  \\
      1 & 2 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3*  \\
      1 & 2 & 3 & 10 & 9 & 8 & 7 & 6 & 5 & 4* \\
      1 & 2 & 3 & 4 & 10 & 9 & 8 & 7 & 6 & 5* \\
      1 & 2 & 3 & 4 & 5 & 10 & 9 & 8 & 7 & 6* \\
      1 & 2 & 3 & 4 & 5 & 6 & 10 & 9 & 8 & 7* \\
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 10 & 9 & 8* \\
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 10 & 9* \\
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10* \\
      1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10
    \end{tabular}
\end{center}

Na primeira linha há 9 comparações, na segunda são 8 e assim por diante. O total de comparações é de:

\[ \sum_{i=1}^9 n = 1 + 2 + \cdots + n = n\frac{n+1}{2}\]

A complexidade é  O$\left(\dfrac{n(n+1)}{2}\right)$ = O($n^2$). O total de comparações é de $\dfrac{9(10)}{2} = \dfrac{90}{2} = 45$ comparações.