Gabarito disponível
public class TicoTeco{
static Integer PASSO_INFERIOR = 200;
static Integer DIVISAO_SUPERIOR = 3;
static Double PI = 3.14;
static Double E_FACT = 2.7;
static Double tico(Integer fronteiraSuperior,
Integer fronteiraInferior) {
Integer novaFronteiraInferior = fronteiraInferior +
PASSO_INFERIOR;
if (fronteiraInferior < fronteiraSuperior) {
teco(fronteiraSuperior, novaFronteiraInferior);
}
return PI;
}
static Double teco(Integer fronteiraSuperior,
Integer fronteiraInferior) {
Integer novaFronteiraSuperior = fronteiraInferior +
((fronteiraSuperior - fronteiraInferior) /
DIVISAO_SUPERIOR);
if (fronteiraInferior < fronteiraSuperior) {
tico(novaFronteiraSuperior,
fronteiraInferior);
}
return E_FACT;
}
}
É correto afirmar que as complexidades dos tempos de execução nos métodos tico e teco, em relação à diferença "fronteiraSuperior - fronteiraInferior", com "fronteiraSuperior" maior que "fronteiraInferior", são iguais a:
Resolução comentada
Ambos os métodos têm complexidade O(log n), pois a diferença cai por um fator constante a cada par de chamadas.
As chamadas formam uma única cadeia de recursão, com uma chamada por nível e custo constante. Em teco, a nova fronteira superior reduz a diferença a cerca de um terço, e em tico o limite inferior avança 200. Assim a diferença diminui geometricamente. O número de chamadas é proporcional a log(n), tanto para tico quanto para teco.
Análise das alternativas
A, B, C e D atribuem O(n) ou O(n log n) a algum dos métodos. Isso é incorreto porque não há laço nem múltiplas chamadas recursivas por nível, e a diferença encolhe em progressão geométrica, não linear.
Referência: Análise de algoritmos recursivos; recorrência T(n)=T(n/c)+O(1).
Resolução comentada do VaiConcursos.