Ah!
Estávamos aprendendo técnicas de lista ligada e recebemos o exercício de encontrar palavras "vizinhas" num dicionário com palavras de três letras. O programa deveria supor que o dicionário está em ordem alfabética.
Vai um amigo meu fazer o programa e pra testar, ele cria outro programa pra fazer o dicionário. Pra isso, ele cria seqüências de três caracteres aleatórios. Faz isso 50 mil vezes. Depois, ele faz um programa que usa o bubblesort para organizar o dicionário.
Ele não entendia por que o programa de sort dele estava demorando tanto nem poor que o programa de achar vizinhos demorava mais ainda. O pior caso apra os dois programas é quando há repetição de valores. Agora, calculem: em média, quantas vezes uma palavra de tr6es eltras deve se repetir numa lista de 50 mil palavras de três letras?