MO417 - Questão para a prova oral

Número: 2009-013

Enunciado: Dados dois algoritmos recursivos Alg₁ e Alg₂, sabe-se que suas relações de recorrência são dadas respectivamente por T₁(n) = 2T₁(n/2) + c₁n e T₂(n) = 4T₂(n/4) + c₂n para entradas de tamanho n > 1. Para entradas de tamanho n = 1, temos T₁(1) = c₁ e T₂(1) = c₂. Assinale a alternativa incorreta:

1. T₁(n)/T₂(n) = O(n).
2. Se c₁ = c₂ o algoritmo Alg₂ é mais rápido, embora não assintoticamente.
3. Alg₁ possui complexidade Θ(n lg(n)).
4. Alg₂ possui complexidade Θ(n^2).
5. NDA

Ideia original de: Ricardo Dutra da Silva