MO417 - Quest?o para a prova oral

N?mero: 013

Enunciado:
Dados dois algoritmos recursivos Alg1 e Alg2, sabe-se que suas rela??es de recorr?ncia s?o dadas respectivamente por T1(n) = 2T1(n/2) + c1n e T2(n) = 4T2(n/4) + c2n para entradas de tamanho n > 1. Para entradas de tamanho n = 1, T1(1) = c1 e T2(1) = c2. Assinale a alternativa incorreta:

  1. T1(n)/T2(n) = O(n).
  2. Se c1 = c2 o algoritmo Alg2 ? mais rápido, embora não assintoticamente.
  3. Alg1 possui complexidade Θ(nlg(n)).
  4. Alg2 possui complexidade Θ(n^2).
  5. NDA

Autor(a): Ricardo Dutra da Silva