3
I need to analyze the time consumption of my algorithm for a size vector 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 counted the instructions of the algorithm. Thus, I arrived at the following recursion:
F(n) = { a, se n =< 1; a + F(n-2), se n > 1
Base: a, if n =< 1 || Step: a + F(n-2), if n > 1
Where "a" corresponds to the sum of the constant instructions.
Second, I expanded 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;
So 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 wonder if I counted the instructions correctly and how to proceed to reach the closed formula.
This empirical count is unreliable. You should use the proof of mathematical induction in this case, only the inductive step was missing. And you could simplify the outcome of
F(n)
with floor function, rounding down.F(n) = a*(1 + floor(n/2))
. I also believe that, given the short circuit, the definition of itsF(n)
has a distinct value ofa
on the basis of the– Jefferson Quesado
Not to mention that this is the longest run time, no palindromes perform faster
– Jefferson Quesado
But have not the inductive step and the base been put? How to consider the best case? Yes, I need to use induction to prove the closed formula
– Kfcaio
Although you don’t use induction to find the closed formula, right? But only to prove it
– Kfcaio
In mathematical induction, there are 3 steps: basis, recursion, inductive step. You have laid the basis is recursion. The inductive step is the way you do to prove that, if it applies to
k
, valley tok+1
.– Jefferson Quesado
For it is, I believe, on a conjecture, you use induction to prove this conjecture.
– Jefferson Quesado
Starting from F(n) as true prove then that F(n+2) is also true? With this I got to F(n+2) = 2a + F(n-2). I am stuck at this point. Does it make any sense? How to proceed?
– Kfcaio
I answered roughly, deserves a greater affection. I hope your point of doubt has been treated correctly and clearly. I expect feedback
– Jefferson Quesado