O interno não percorrerá em n * n
, em nenhum lugar mostra isso e é uma inferência sua que faz isso. Já que essa informação não existe no código, você que deveria dizer porque achou isso.
Se tem apenas um laço interno não tem como ele por si só ser polinomial. A não ser que alguma função interna nele na verdade fosse um laço mesmo sem você saber, mas não é o caso, todas funções (e operadores) executadas ali dentro tem complexidade O(1).
Inclusive dizer que é O(n^2) também está errado. A fórmula correta aproximada seria O(n*(n/2)) já que a cada passo ele vai começando percorrer os elementos mais pra frente até que no fim ele começa pelo último elemento, na média ele executa metade dos elementos.
O laço externo vai de 0 até o tamanho da coleção passada. Isso é fácil. Vamos dizer que a coleção tenha 6 elementos, portanto a faixa vai até 5, ela é exclusiva.
O laço interno primeiramente começará em 1 e vai até o 5. No segundo passo do externo o valor de i
é 1, então o próximo laço interno começará do 2 e vai até 5. Na próxima vai do 3 até 5, e assim continua até que vai do 5 até 5. Portanto o primeiro percorreu 5 elementos, depois 4, então 3, aí 2, e finalmente 1. Somando tudo dá 15, e para calcular a média dividimos pela quantidade de interações (que foram 5), que dá 3, e que é metade de 6.
Eu dei uma resposta que mostra isso com mais detalhes e um exemplo. Ali fica mais claro a desmistificação que a quantidade de laços usada sempre determina a complexidade. Em alguns casos sim, por isso não serve de modelo, serve como indicação inicial a ser investigada mais. Nos comentários da outra resposta eu mostro como o que parece ser uma complexidade pode ser outra se for mais a fundo, e coincidências não podem ser usadas para demonstrar a complexidade real.
Coloquei no GitHub para referência futura.