MO417 - Questão para a prova oral

Número:

Enunciado: Dado o seguinte algoritmo para fazer a busca do i-ésimo menor elemento:

RANDOMIZED-SELECT(A, p, r, i)
1  if p == r
2       return A[p]
3       q = RANDOMIZED-PARTITION(A, p, r)
4  k = q - p + 1
5  if i == k  // the pivot value is the answer
6       return A[q]
7  elseif i < k
8       return RANDOMIZED-SELECT(A, p, q - 1, i)
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

Se T(n) representa o tempo de execução do algoritmo RANDOMIZED-SELECT e S(n) representa o tempo de execução do algoritmo RANDOMIZED-SELECT trocando a linha 3 por uma partiçao que não seja aleatória, qual das seguintes afirmações é correta:

A) No pior caso T(n) = Θ(n) e  S(n) = Θ(n)
B) No pior caso T(n) = Θ(n²) e  S(n) = Θ(n²)
C) No caso médio T(n) = O(n) e  S(n) = O(n)
D) No caso médio T(n) = Θ(n²) e  S(n) = Θ(n²)
E) NDA

Ideia original de: John Edgar Vargas Muñoz