Retrocomputação de Verdade #1

Quando eu falo que gosto de retrocomputação, a maioria das pessoas assume que eu estou falando de TK90X e MSX. Mas para mim esses aí não são retrocomputação, são só computação. Eu usei essas máquinas quando elas eram o que havia de melhor (na minha faixa de preço). Antes delas, porém, teve uma época mágica onde computadores eram grandes, barulhentos e ocupavam salas inteiras!

Sempre que eu estou viajando por aí, aproveito a oportunidade para visitar museus de ciência e conhecer esses grandes retrocomputadores do passado. Mas só ver de perto eu não acho tão legal, o que completa a experiência é entender como eles funcionam! Minha idéia original era falar sobre todos os retrocomputadores que já conheci, mas, como ficaria muito grande, vou começar só com os retrocomputadores mecânicos:

O Mecanismo de Antikhytera, 200-100 AC.

Museu Arqueológico Nacional, Atenas, Grécia

A maior prova da engenhosidade grega, o Mecanismo de Antikhytera é muitas vezes chamado de o primeiro computador. Quer dizer, é um computador analógico não-reprogramável, hoje em dia estaria mais próximo do que a gente chama de calculadora.

E para que ele serve? O Mecanismo tem a função de calcular intervalos de tempo: você gira uma manivela que aciona o ponteiro dos anos, e ele ajusta sozinho os outros ponteiros, que são muitos. Ele calcula o mês, a fase da Lua, a posição dos planetas, os eclipses mais próximos, a data da Olimpíada, a constelação do Zodíaco e assim por diante.

Todos esses cálculos são baseados em engrenagens dentadas. Se você tem uma engrenagem com x dentes ligadas a outra com y dentes, a segunda vai rodar com velocidade angular igual a x/y da original. Então você só precisa saber a razão entre a duração de um mês e um ano para fazer um ponteiro que indica o mês.

Mas os gregos eram realmente espertos, e sabiam que algumas relações você não consegue fazer só com razões. A posição da Lua, por exemplo. Eles sabiam que a Lua anda mais devagar em alguns trechos que em outros (por causa do que hoje conhecemos como segunda Lei de Kepler), e, para simular esse efeito, eles fazem uma das engrenagens não ter o centro fixo, assim ela tem velocidade angular variável com a posição.

E como sabemos tanto sobre ela, dado que só temos pedaços de um exemplar que foi achado em um naufrágio? É que um dos pedaços era o manual!

Olhe as inscrições em grego

Essa é a parte legal de visitar museus e ver essas coisas de perto, dá para prestar atenção nos detalhes!

O Motor de Diferenças, 1822

Museu da História da Computação, Mountain View, USA

O século XIX foi a época do Maxwell, Faraday, Tesla, Edison. A engenharia elétrica estava bombando! Mas, para fazer os circuitos funcionarem, você precisa saber resolver equações diferenciais bem complicadas. Essas contas eram resolvidas com tábuas de logaritmos que simplificavam bastante o processo. Mas quem criava as tábuas de logaritmos?

Em geral elas eram feitas por um batalhão de pessoas que calculavam logaritmos na mão, com seis ou sete dígitos significativos. É um trabalho repetitivo e propenso a erros. Hoje em dia nós sabemos que a melhor maneira de realizar cálculos repetitivos e propenso a erros é um computador, mas o primeiro a ter essa idéia foi o Babbage, em 1822. Nessa época ele conseguiu o financiamento para construir o Motor de Diferenças, que tem uma única finalidade: calcular polinômios. Assim ele teria como aproximar os logaritmos por séries de Taylor equivalentes.

Depois de sugar dinheiro do governo por vinte anos sem entregar nada, o financiamento foi cortado. (O governo percebeu que com aquela dinheirama toda dava para contratar gente o suficiente para calcular os polinômios e conferir as contas). Mas foi uma pena, porque o projeto do Babbage era sólido. Se tivesse sido terminado, nunca mais alguém precisaria fazer esse tipo de conta.

Mas será que o Babbage teria conseguido terminar, se não tivesse perdido o contrato? Em 1985, cientistas resolveram seguir o projeto original e montar um Motor de Diferenças de verdade. Eles descobriram que o projeto tinha pequenos erros, mas os erros eram tão bobos que certamente foram introduzidos de propósito, como forma de proteção contra cópia (a técnica de introduzir erros como proteção contra pirataria foi usada desde a Renascença, quem costumava fazer isso era o Leonardo da Vinci). Corrigindo os erros propositais, o Motor funciona! Atualmente tem duas réplicas em funcionamento, uma em Londres e outra na Califórnia.

Por dentro, o Motor de Diferenças também funciona com engrenagens como a Mecanismo de Antikhytera, mas com uma diferença fundamental. O Mecanismo codificava a informação como um ângulo da engrenagem, se você quisesse mais precisão, precisava aumentar fisicamente o tamanho da engrenagem. O Babbage queria precisões de sete dígitos significativos, aí esse método é inviável. A solução foi abandonar a codificação analógica e usar engrenagens digitais. Cada engrenagem marca um dígito de 0 a 9, e com sete engrenagens em sequência você codifica os sete dígitos desejados.

Duas engrenagens encaixadas implementam adição ou subtração (já que virando uma delas, a outra vira junto). Mas, se são engrenagens digitais, então falta um detalhe importante: o vai-um. Eu gravei o vídeo abaixo mostrando o carry propagando, garanto que é a coisa mais bonita que você vai ver hoje!

Propagação mecânica de carry

A Bomba de Turing, 1940

Bletchley Park, UK

Sobre a história desse computador eu não preciso falar muito, já que ela foi transformada em um filme: O Jogo da Imitação (tem no Netflix). Eles precisaram transformar a história do Turing num romance heterossexual para ficar palatável para as massas, mas tá valendo, pelo menos agora as pessoas sabem quem foi o Turing.

A máquina que ele criou era conhecida entre eles como a Bomba. Ela tinha uma única função: quebrar o código de criptografia da máquina alemã Enigma, então para entender a Bomba você precisa entender o Enigma antes. As primeiras versões do Enigma era assim:

O Enigma

O coração do Enigma são os rotores (as engrenagens à esquerda, na foto). Ao longo do rotor está sequência alfabética misturada. Quando inserida no slot apropriado, o rotor faz uma cifra de permutação, obedecendo uma tabela como essa:

Ou seja, a letra A no original vira Z, a letra B vira P, e assim por diante. Quebrar esse código é fácil, qualquer criança esperta consegue. Mas o Enigma é mais seguro que isso. Ao invés de um único rotor, ele tem três rotores em sequência, e os três são diferentes: a letra A vira Z, depois no rotor seguinte você pega esse Z e vira F, depois no último o F pode virar Q. E, para complicar mais, cada vez que você aperta uma tecla o rotor gira, ou seja, dá um offset de uma letra no primeiro rotor. Quando o primeiro rotor gira por completo, induz o segundo a girar uma posição, e assim por diante.

Bastante complicado né? Mas isso não é seguro o suficiente em um contexto de guerra mundial. A senha desse sistema é a configuração inicial dos rotores. Você pode encaixar os rotores no slot em qualquer ordem (6 combinações), e iniciando em qualquer ângulo inicial (26^3 combinações). Isso dá um total de 105456 senhas possíveis. Ninguém consegue testar todas essas senhas em um dia. Mas, também, ninguém precisa testar sozinho! É só pegar 105456 soldados e mandar cada um testar uma senha diferente. Um deles vai acertar de primeira! (E 105 mil soldados não é muito, é só lembrar que no Maracanã cheio cabem 80 mil pessoas. 105 mil soldados é um Maracanã e meio só).

Por isso os alemães colocaram na frente da máquina uns plugues adicionais, que servem para permutar letras na entrada. Se você liga um plugue da posição A para a R, então a letra A vira R e a letra R vira A. Eles usavam em média uns dez plugues, então o número de senhas sobe de 105 mil para 100 bilhões. Parece uma solução esperta, mas isso, na verdade, foi uma burrice dos alemães! Desse jeito, é garantido que a letra A nunca vai virar A de novo. Então eles aumentaram o número de chaves, mas diminuíram o espaço de busca.

Agora já dá para entender a Bomba de Turing. A Bomba, na verdade, é um emulador de Enigma (o Turing sempre foi fã de emuladores, seu conceito de máquina universal é basicamente um emulador genérico). Ele tem todos os rotores iguais aos do Enigma, e um motor que gira os rotores em todas as posições possíveis, bem rapidamente. Atrás de cada rotor tem um contato elétrico: se você colocar uma palavra codificada de um lado, e uma palavra traduzida do outro, quando os rotores giraram na posição correta, dá o contato e ele avisa que achou a senha. E na prática ele não precisa girar todas as combinações possíveis. Se em alguma rotação tiver uma letra que foi mapeada nela mesma, você pode cortar a árvore de busca, porque essa senha com certeza está errada.

Então tudo que resta para quebrar o Enigma é achar um par de palavras, uma codificada, e sua correspondente não-codificada. Isso é o que hoje em dia chamamos de known-plaintext attack. Parece difícil, mas existiam vários truques para conseguir pares assim.

Um deles era baseado no tamanho da mensagem máxima dos alemães. Quando estourava o limite de tamanho, eles quebravam a mensagem em duas, e a segunda parte começava com "continuando, ...". Então, quando encontravam pacotes de várias mensagens longas, uma seguida da outra, certeza que uma delas começaria com "Fortsetzung".

Outra maneira era colocando minas explosivas no meio do mar. Os aliados colocavam as minas de um jeito fácil de encontrar, e em um lugar conhecido. Aí era só esperar os alemães acharem as minas. Quando eles achavam, transmitiam as coordenadas pelo rádio, então era só colocar as coordenadas da mina no computador, que eventualmente ele iria achar uma mensagem correspondente.

Quem viu o filme do Turing deve lembrar que no final eles jogam tudo numa fogueira. Isso aconteceu mesmo, quase tudo sobre o projeto foi destruído, e o que não foi era classificado como ultra-secreto. Só na década de 70 é que o mundo descobriu a existência das Bombas de Turing, e hoje em dia temos informação suficiente para recriar uma delas, como essa que está exposição no Bletchley Park.

A Bomba de Turing por dentro

Ainda tem mais computadores que eu conheci de perto, mas os outros ficam para a parte 2 :)

Livros de Colorir são Equivalentes a Sudoku

De tempos em tempos a mídia impressa inventa uma modinha para vender mais papel. A modinha da vez são os livros de colorir. Eles são uma sensação! Os livros não param nas lojas, existem grupos e grupos falando disso na internet, rola até competição para ver quem pinta melhor!

Mas, se você tem memória boa, deve lembrar que mesma coisa aconteceu dez anos atrás. Ao invés de livros de colorir, a modinha era Sudoku. Era uma sensação! Haviam livros e livros nas lojas, todo mundo falava disso na internet, rolava até competição para ver quem resolvia mais rápido!

À primeira vista, os dois passatempos são bem distintos: o livro de colorir precisa de sensibilidade artística, o sudoku de raciocínio lógico. Mas hoje eu vou provar que, na verdade, os dois são equivalentes! E tudo começa com a regra não escrita dos livros de colorir.

A Regra dos Livros de Colorir

Livros de colorir tem uma regra implícita. Todo mundo concorda que isso aqui é uma pintura válida, certo?

  

Mas isso aqui é trapacear:

 

A regra implícita dos livros de colorir é que pintar duas regiões adjacentes com a mesma cor não vale. Afinal, tem uma linha preta ali, e ela está ali por uma razão, que é separar regiões de cores diferentes. Se você ignorar a linha preta, não está aproveitando todos os detalhes da figura.

Se você for a uma papelaria atualmente, verá que todas as caixas de lápis de cor com 48 cores estão esgotadas. O motivo é que os livros de colorir tem muitas regiões adjacentes, então quanto mais cores, mais fácil de pintar.

E qual é o mínimo de cores que você precisa? Um estojo de 12 cores é suficiente? Incrivelmente, doze cores dá e sobra. Na verdade, com apenas 4 cores você consegue pintar qualquer desenho, sem deixar regiões adjacentes com a mesma cor! Essa proposição é o lendário Teorema das Quatro Cores, que ficou famoso por ter sido o primeiro grande teorema da matemática provado por computador.

Além disso, o problema de pintar um desenho com a menor quantidade de cores possíveis não é apenas teórico. Ele tem várias utilidades práticas! Por exemplo, compiladores usam pintura para fazer alocação de registros, e companhias aéreas usam pintura para fazer alocação de aviões em rotas aéreas.

O problema da pintura mínima também serve para resolver Sudokus. Mas antes de mostrar como isso pode ser feito, vamos resolver um problema mais simples, o Bidoku.

Bidoku

O Bidoku é a versão fácil do Sudoku. Você tem um grid 2x2, e precisa preenchê-lo com 0 e 1, de modo não tenha dois números iguais na mesma linha e na mesma coluna:

 

Esse puzzle é bem fácil, dá para resolver de cabeça né? Mas vamos ver como é o raciocínio usando pintura. Para isso, vamos dar um nome para cada uma das células do puzzle:

 

Cada uma das letras pode ser 0 ou 1. Vamos enumerar as possiblidades: A pode ser 0 ou 1, B pode ser 0 ou 1, e assim por diante:

 

Agora vamos ligar com uma linha todos os nós que não podem acontecer ao mesmo tempo. Começando do B, nós sabemos que ou o B é zero, ou o B é um. Então coloco uma linha entre B0 e B1. Além disso, se B for 0, então nem A e nem C podem ser 0. Da mesma maneira, se B for 1, então nem A e nem C podem ser 1. Desenhando:

 

Agora é só repetir o que fizemos com o B para todas as outras letras:

 

Este é o grafo equivalente do Bidoku. Com o grafo em mãos, podemos achar a figura de colorir equivalente, basta achar um desenho onde as regiões adjacentes são exatamente aquelas indicadas pelas linhas do grafo. Qualquer desenho que satisfaça essa condição serve, pode ser esse aqui, por exemplo:

 

Com o desenho em mãos, podemos resolver o Bidoku através da coloração!. Começa assim: você pega todos os números que foram dados, e pinta de verde. No Bidoku exemplo acima, era dado que o A valia 1, então nós pintamos de verde o A1:

 

Agora é só pintar o restante com o menor número de cores possível, respeitando a regra de que regiões adjacentes precisam ter cores distintas. Se você fizer a pintura, vai notar que é possível pintar com apenas duas cores, de uma única maneira:

 

Agora você pega todas as regiões verdes e retorna para o Bidoku original:

 

Funciona mesmo! O Bidoku foi resolvido pela coloração mínima!

Uma dúvida pertinente é o que acontece com a coloração se você tentar pintar um Bidoku insolúvel. Por exemplo, o Bidoku abaixo não tem solução (o B não pode ser 0 e nem 1):

 

Se você tentar a coloração mínima, vai notar que são necessárias no mínimo três cores para respeitar as regras:

 

Essa regra vale sempre, se a sua coloração mínima tem mais de duas cores, então o Bidoku original era insolúvel.

Agora que já dominamos o Bidoku, podemos passar para a solução do Sudoku.

A Coloração do Sudoku

O Sudoku usa o mesmo raciocínio do Bidoku, mas o problema é muito maior. No Bidoku a célula A tinha duas possibilidades, então nós criávamos dois nós: A0 e A1. No Sudoku, ela tem nove possibilidades, então a célula A gera os nós A1, A2, A3, .., até A9. E você precisa adicionar linhas ligando os números, as linhas, as colunas, e as caixas (eu chamo de caixas aqueles blocos 3x3). O grafo final do Sudoku, levando em conta tudo isso, fica assim:

Clique na imagem para ver o SVG original

São 729 nós e 11664 linhas, só um pouquinho maior que o Bidoku, que tinha 8 nós e 12 linhas. Além disso, no Bidoku nós conseguimos fazer um desenho equivalente ao grafo. No Sudoku isso não é possível, porque esse grafo não é planar (ou melhor, você pode fazer um desenho, mas vai ser um desenho multidimensional em uma geometria possivelmente não-euclideana). Isso não afeta nossa proposição, já você pode colorir diretamente os nós do grafo, ao invés de colorir as regiões de um desenho equivalente.

E como fazemos isso? Da mesma maneira que o Bidoku, você parte de um Sudoku que você quer resolver, por exemplo esse aqui, que eu peguei no The Guardian:

 

Nós vamos pintar de verde todas as células correspondentes no grafo do Sudoku (eu não vou mostrar as linhas dessa vez, assim fica mais visível):

Clique na imagem para ver o SVG original

Pois bem, a minha proposição é que se você fizer a pintura mínima nesse grafo, o resultado do Sudoku vai aparecer nas células que forem pintadas de verde. Nós vimos um exemplo de que isso funciona no Bidoku, mas um exemplo não é uma demonstração, pode ter sido coincidência. Eu vou provar abaixo que isso sempre é verdade. Se você tem medo de demonstrações, pule a caixa azul para ver o Sudoku pintado.

Antes de mais nada, quantas cores precisamos para pintar esse grafo? O instinto é falar que precisamos de 4 cores, por causa do Teorema das Quatro Cores. Mas esse teorema só funciona se o grafo for planar! E o grafo do Sudoku claramente não é planar, já que ele admite o K₅ como subgrafo, e, portanto, viola o teorema de Kuratowski para grafos planares.

Vamos tentar achar qual o número de cores então. Pegue uma célula qualquer, por exemplo uma célula A. Nós temos 9 nós correspondentes, de A1 até A9, e nenhum desses nós pode ter a mesma cor que o outro. Então o grafo da célula A é um clique de tamanho 9. Como o número cromático de um grafo é sempre maior ou igual ao grau do maior clique, então sabemos que o grafo tem pelo menos 9 cores.

Mas, se esse grafo foi construído a partir de um Sudoku que tem solução, então nós podemos construir uma coloração com 9 cores para ele. Você começa pintando todos os nós da solução com a cor 0. Depois, para cada tripla (i, j, digito) que foi pintada com a cor 0, você pinta a tripla (i, j, digito + 1) com a cor 1 (o incremento no dígito é mod 9). Essa pintura não viola o grafo, porque ele é simétrico nos dígitos. Repetindo o processo para as cores 2..9, você tem um grafo totalmente pintado e sem nenhuma violação.

Se o número mínimo de cores é 9, e nós sempre conseguimos construir uma pintura com 9 cores, então o número cromático é 9. Done.

Ainda falta um detalhe: ninguém garante que existe uma única pintura possível com 9 cores (e na prática vai ter mais de uma mesmo). Mas todas as pinturas possíveis resolvem o Sudoku! Como o número cromático é 9, então cada célula (i,j) vai ter um elemento pintado com cada uma das cores possíveis (já que a célula é um clique de tamanho 9). Como cada célula tem todas as cores, então cada célula vai ter um elemento com a cor 0; e se todas as células tem a cor 0, então toda pintura possível embute uma solução do Sudoku. QED.

Se você tiver paciência de fazer a pintura mínima naquele grafo gigante, o resultado será esse aqui:

Clique na imagem para ver o SVG original

Transcrevendo as células verdes para o diagrama original, temos a solução do Sudoku, como prometido!

 

Na prática, esse é provavelmente um dos piores métodos para resolver o Sudoku. Mesmo um algoritmo no estado da arte em graph coloring vai levar um bom tempo para achar uma solução através de pintura mínima. Mas pelo menos você pode dizer que Sudoku é equivalente a um livro de pintura, desde que você não ligue de fazer pinturas mínimas em livros multidimensionais de geometria possivelmente não-euclideana :)

   

A Intuição do Knuth

Às vezes eu me pergunto se as pessoas da minha área têm noção de quão sortudos nós somos. Os físicos adorariam viajar no tempo para conversar com o Newton, os matemáticos adorariam conversar com o Euclides, os biólogos adorariam conversar com o Darwin. Mas nós podemos conversar com o Knuth!

Nós temos a sorte de viver no mesmo período de tempo que o criador da análise de algoritmos, que é uma das bases da Ciência da Computação. Se você gosta do assunto, vale a pena juntar uns trocos e viajar até a Califórnia para assistir a uma das palestras dele (dica: todo fim de ano, inspirado nas árvores de Natal, ele faz uma palestra de estrutura de dados, falando sobre árvores; elas também estão online se você não tiver como ver ao vivo).

Eu fiz a peregrinação em 2011, quando consegui assistir a uma das palestras dele. Aproveitei para ir todo contente pegar minha recompensa por ter achado um erro no Art of Computer Programming, mas ele, marotamente, me disse que aquilo que eu achei não era um erro, era uma pegadinha, e eu caí! (Mas eu não vou falar qual a pegadinha, vá na página 492 do TAOCP volume 4A, primeira edição, e confira você mesmo :)

Eu e Knuth, o trollzinho

Nesse dia perguntaram que opinião ele tinha sobre o problema mais difícil da nossa geração, P=NP. A intuição dele é que provalmente é verdade, mas ele acredita que se acharmos a demonstração, ela vai ser não-construtiva. O que isso significa? O que é uma demonstração não-construtiva?

Demonstrações construtivas e não-construtivas

Em análise de algoritmos, as demonstrações construtivas são as mais comuns. Por exemplo, digamos que eu quero provar que é possível calcular x elevado a y em tempo O(y). Isso é fácil, basta construir um algoritmo assim:
E se eu quiser provar que esse mesmo problema pode ser resolvido em tempo O(log y)? Novamente, tudo que eu preciso fazer é exibir um algoritmo que implemente isso:

(Nesse caso eu também precisaria provar que esse algoritmo é de fato O(log y), já não é óbvio por inspeção). Nos dois casos temos exemplos de demonstrações construtivas: se eu quero provar uma propriedade P, basta exibir um algoritmo que tenha essa propriedade P.

As demonstrações não-construtivas são diferentes. Nelas, eu posso provar a propriedade P sem mostrar o algoritmo, através de alguma propriedade matemática do modelo.

Por exemplo, imagine que eu tenho uma lista ordenada de números. Se eu fizer uma busca binária, posso achar a posição de um número dado com O(log n) comparações. Mas é possível criar um algoritmo mais rápido que isso? Eu digo que não é possível, e para isso vou fazer uma prova não-construtiva de que esse é o mínimo que um algoritmo de busca precisa para funcionar.

A Teoria de Shannon aplicada à busca binária

Para isso eu vou usar a teoria da informação de Shannon. Essa teoria é surpreendentemente intuitiva, e se baseia no conceito de surpresa. Se eu te falar que o céu ficou escuro às 19h, você não vai achar nada de mais, nessa hora o Sol está se pondo, então é natural que o céu fique escuro. Mas e se eu falar que o céu ficou escuro às 10 da manhã? Foi uma tempestade? Um eclipse? A nave do Independence Day?

Intuitivamente, quanto mais surpresos nós ficamos com uma sentença, mais informação ela tem. O Shannon definiu então a quantidade de informação como sendo uma função monotônica da probabilidade do evento acontecer:

Se o evento é raro, tem bastante informação; se o evento é comum, tem pouca informação. A base do logaritmo fornece a unidade de medida, se a base for 2, então a informação é medida em bits.

E quanta informação nós ganhamos com uma comparação? Se a chance de dar verdadeiro ou falso for a mesma, então a chance é p(m)=1/2, logo a informação é I(m)=1. Você ganha exatamente um bit de informação com uma comparação.

Qual o resultado do nosso algoritmo de busca? O resultado é um índice, se nós temos n elementos no vetor, então a resposta é um índice que varia de 0 a n-1. Logo, a probabilidade de você escolher o índice certo ao acaso é p(m)=1/n, já que a escolha é uniforme.

Quanta informação tem essa escolha, então? Fazendo a conta:

Se você precisa de log n bits para descrever a resposta, e você ganha só 1 bit por comparação, então não tem como um algoritmo rodar em menos que O(log n): a informação tem que vir de algum lugar! Com isso, nós mostramos que qualquer algoritmo precisa rodar no mínimo em tempo O(log n), e sem precisar mostrar o algoritmo em si. Essa é uma demonstração não-construtiva.

Pressinto a pergunta: "mas RicBit, e a busca com hash table, ela não é O(1)?". Sim, ela é! Mas ela não usa comparações, e a nossa análise foi exclusivamente para métodos baseados em comparações. Com um acesso a uma hash você pode ganhar mais que 1 bit de informação por operação.

O limite da ordenação

Um outro exemplo é achar o limite dos algoritmos de ordenação. Suponha que eu tenho um vetor com elementos bagunçados e quero ordená-los usando comparações. Eu sei que cada comparação ganha 1 bit de informação, então só preciso saber quanta informação tem na saída.

Qual o resultado do algoritmo? Um vetor ordenado. Mas os valores do vetor em si são irrelevantes, o que importa mesmo é saber a ordem relativa entre eles. Essa ordem relativa pode ser expressa como uma permutação dos itens originais.

Quantas permutações existem? Se o vetor tem tamanho n, então existem n! permutações, logo a probabilidade é 1/n!. Fazendo as contas:

Primeiro você usa a aproximação de Stirling, depois joga fora todos os termos assintoticamentes menores que o dominante. O resultado é que nós provamos que nenhuma ordenação pode ser melhor que O(n log n), sem precisar mostrar nenhum algoritmo!

Novamente, esse resultado só vale para ordenações baseadas em comparações. Sem usar comparações, você tem métodos como radix sort e ábaco sort que são melhores que O(n log n).

A análise por quantidade de informação

Esse método de análise da quantidade de informação pode ser utilizado em qualquer algoritmo, desde que você note um detalhe muito importante: o método acha um limite inferior para a complexidade, mas não prova que esse algoritmo existe! Tudo que conseguimos provar como ele é que, se o algoritmo existir, então ele não pode ser melhor que o limite achado.