MO417 - Questão para a prova oral

Número: 2010-007

Enunciado: Com o intuito de melhorar o desempenho do algoritmo Merge-Sort, foi proposto um novo algoritmo que ao invés de subdividir o problema inicial em 2 subproblemas de igual tamanho entre si (e assim sucessivamente), subdivide o problema inicial em 3 subproblemas de igual tamanho entre si (e assim sucessivamente). Este novo algoritmo possui um tempo de execução da ordem de?

1. Θ(n)
2. Θ(nlog n)
3. Θ(n²)
4. Θ(n²log n)
5. NDA

Ideia original de: Leonardo Scanferla Amaral