MO417 - Questão para a prova oral

Número: 2010-026

Enunciado: Na prova do limite inferior para ordenações por comparação são usadas árvores binárias cheias para mostrar que todo algoritmo de ordenação por comparação vai usar Ω(n lg n) comparações. As árvores usadas tem as seguintes características:

1. Para cada algoritmo existe uma árvore, que é a mesma para todos os tamanhos de entrada, e cada caminho da raiz até uma folha é uma execuçãs diferente do algoritmo.
2. Para cada entrada de tamanho n existe uma árvore, que é compartilhada por todos os algoritmos, e cada algoritmo faz um caminho próprio nela.
3. Para cada tamanho n e para cada algoritmo existe uma árvore, e cada caminho da raiz até uma folha é uma execuçãs diferente do algoritmo.
4. Existe uma única árvore para qualquer tamanho de entrada e para qualquer algoritmo, e o caminho feito nessa árvore vai depender do algoritmo e do tamanho da entrada.
5. NDA

Ideia original de: Alexandre Tachard Passos