I need to analyze the time consumption of my algorithm, for a vector of size n = f - i + 1
, through a recursion, to then define a closed formula.
public class ehpalindromo {
public static boolean ehPalindromo(String palavra, int i, int f) {
//verificar se palavra vazia é vetor unitário com espaço ou vetor vazio(enter)
boolean iguais = palavra.charAt(i) == palavra.charAt(f); //t1 + t2
return iguais && (f - i <= 2 ? true : ehPalindromo(palavra, i + 1, f - 1)); //t3 + t4 + t5 + (t6)
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Digite uma palavra para verificarmos se eh um palindromo ou nao: ");
String palavra = sc.nextLine();
System.out.println("Digite o início e o fim da sequência a ser analisada: ");
int i = sc.nextInt();
int f = sc.nextInt();
if(ehPalindromo(palavra, i, f)){
System.out.println(palavra + " eh palindromo");
}else {
System.out.println(palavra + " nao eh palindromo");
}
}
}
First, I told the algorithm instructions. So I came up with the following recursion:
F(n) = { a, se n =< 1; a + F(n-2), se n > 1
Basis: a, if n = < 1 || Step: a + F (n-2), if n> 1
Where "a" is the sum of the constant statements.
Second, I expanded the recurrence:
F(0) = a; F(1) = a; F(2) = a + F(0) = a + a = 2a; F(3) = a + F(1) = a + a = 2a; F(4) = a + F(2) = a + 2a = 3a; F(5) = a + F(3) = a + 2a = 3a; F(6) = a + F(4) = a + 3a = 4a;
In this way, I came, empirically, to the closed formula:
F(n) = a + (n/2)a; porém, esta só funciona quando n é par, pois para n impar, ela seria F(n) = a + ((n-1)/2)a.
I would like to know if I counted the instructions correctly and how to proceed to get the formula closed.