MO417 - Questões para a prova oral

Número: 2009-020

Enunciado: Considere o pseudo-código abaixo que retorna o índice do elemento mínimo do vetor v = (v[i], . . . , v[f]), onde i ≤ f:

minimo (v, i, f)
1.   if i = f
2.     then return i
3.   p ← minimo (v, i, (i+f)/2)
4.   q ← minimo (v, (i+f)/2+1, f)
5.   if v[p] ≤ v[q]
6.     then return p
7.   return q

Considerando n = f - i + 1, o número de comparações entre elementos de v numa execução de minimo ( v, i, f) é?

1. n log n
2. n - 1
3. n/2
4. log n
5. NDA

Ideia original de: Ana Carolina Correia Rézio