MO417 - Questão para a prova oral

Número: 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

Autor(a): Ana Carolina Correia Rézio