MO417 - Questão para a prova oral

Número:

Enunciado: Considere uma variação do Bubblesort com o seguinte funcionamento: Dado um vetor A[1...n], nas iterações ímpares o bubblesort comum é executado, já nas iterações pares o bubblesort é executado no sentido contrário, ou seja, do final do vetor para o começo. Dado a entrada do pior caso do algoritmo de Bubblesort comum, qual o tempo de execução para essa entrada no algoritmo de Bubblesort alterado?

A) ϴ(n)

B) ϴ(n²)

C) ϴ(nlgn)

D) ϴ(n³)

E) N.D.A

Ideia original de: Thaís Harumi Ussami