Temporal complexity of recursive palindrome algorithm

3

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.

    
asked by anonymous 25.09.2017 / 21:44

1 answer

2

To demonstrate a formula derived from recurrence, you need the conjecture (the derived formula defined above, which we want to prove) and 3 other features:

  • Recurring formula;
  • Recursion Basis;
  • Inductive step.
  •   

    As the AP has already demonstrated knowledge of the first two points, I will not go into detail now.

    Inductive pitch

    Suppose the conjecture works for f(x) ; using recursion, we proved that it also works for f(x + 1) .

    In this case, the conjecture is, in this case:

    AssumingthisistrueforF(x).Toevaluateax+2palindrome,itwillbenecessarytodoamoresteps(givenbytherecurringformula).Therefore:

      

    CQD.

    The inductive step works for F(0) and F(1) , so the conjecture proves correct.

    Demonstrate the inductive step valid for F(0) and F(1) remains as homework for the reader ;-)

        
    26.09.2017 / 00:34