087-2008

MO640 - Questão para a prova oral
Número: 087
Enunciado:
Sobre o algoritmo de Bader, Moret e Yan para o cálculo de distância de reversão de permutações de tamanho n, podemos afirmar que:

1. Seu limitante inferior de tempo é O(n²).
2. Ele executa em O(n) para a maioria dos casos, mas não para todos.
3. Ele calcula a distância e os passos da ordenação em tempo O(n).
4. Ele calcula a distância em complexidade O(n) mas não calcula os passos da ordenação.
5. NDA.

Autor(a): Danilo Brandão Gonçalves