Questão
ID 1913336Disciplina: Tecnologia da Informação
Assuntos: Complexidade de Algoritmos (Big-O, P x NP)
Ano: 2016 Banca: IFPI - Instituto Federal do Piauí Órgão: Instituto Federal de Educação Ciência e Tecnologia do Piauí
Considere o código-fonte que segue:
int f1(int n) {
if (n == 0 II n == 1) return n;
else return (2 * f1(n-1) + 3 * f1(n-2)); }
int f2(int n) {
int a; int[] X = new int [n];
int[] X = new int [n]; int[] Z = new int [n];
X [0] = Y [0] = Z [0] = 0;
X [1] = 1; Y [1] = 2; Z [1] = 3;
for (a = 2; a <= n; a ++) {
X [a] = Y [a-1] + Z [a-2];
Y [a] = 2 * X [a]; Z [a] = 3 * X [a]; }
return X [n];
Qual é o tempo de execução de f1(n) e f2(n), respectivamente?