MO417 - Questão para a prova oral

Número: 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 subploblemas (e assim sucessivamente), subdivide o problema inicial em 3 (e assim sucessivamente). Dado que este novo algoritmo realmente ordena o vetor de entrada, a pergunta é: este novo algoritmo possui um tempo de execução na ordem de?

  1. Θ(n)
  2. Θ(nlog n)
  3. Θ(n2)
  4. Θ(n2log n)
  5. NDA

Autor: Leonardo Scanferla Amaral