Time complexity of recursive palindromic algorithm

Asked

Viewed 420 times

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.

java recursion

  • 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 its F(n) has a distinct value of a on the basis of the

  • Not to mention that this is the longest run time, no palindromes perform faster

  • 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

  • Although you don’t use induction to find the closed formula, right? But only to prove it

  • 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 to k+1.

  • For it is, I believe, on a conjecture, you use induction to prove this conjecture.

  • 1

    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?

  • I answered roughly, deserves a greater affection. I hope your point of doubt has been treated correctly and clearly. I expect feedback

Show 3 more comments

1 answer

3


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:

  1. Recurring formula;
  2. Basis of the recursion;
  3. Inductive step.

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

Inductive step

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

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

F(x) = a*(1 + floor(x/2))

Supposing it’s true for F(x). To evaluate a palindrome of size x+2, it will be necessary to do a extra steps (given by the recurring formula). Therefore:

F(x+2) = a + F(x) = a + a*(1 + floor(x/2)) = a*(1+1+floor(x/2)) = a*(1+floor( (x+2)/2 ))

QED.

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

Demonstrate valid inductive step to F(0) and F(1) is like homework for the reader ;-)

  • Jefferson, the problem is in the fact that I cannot use the floor function, because our test will not be programmed. How can I replace it?

  • Using mathematical notation that looks like a square bracket without the top; https://en.wikipedia.org/wiki/Floor_and_ceiling_functions?wprov=sfti1; this is a mathematical function that is not properly described for real and rational ones. The Math.floor comes from the direct mathematical description, not something invented only in the field of programming languages

  • So, is F(n) = a + F(n-2) also part of the base? And not just F(0) and F(1)? So the recursion would be F(n) = ((n/2)+1)a ? You can mark each of these parts in your reply, please?

  • Base are only F(0) and F(1), I thought you already understood this concept, but I was wrong. F(n) = F(n-2) + a is a consequence of the recursive formula, but it only applies to n>=2. In order for the recursive/recurrence formula to address the entire natural domain, it is usually written F(n+2) = F(n) + a. With the exception of the above described definitions, everything else is in the properly highlighted answer. Quit F(0) and F(1) with the inductive step has been deleted from my reply by: (a) triviality, very simple to do; (b) provide quick help.

  • Demonstrate valid inductive step to F(0) and F(1) is like homework for the reader ;-)

  • 1

    @Caioignm , with Latex formulas making everything more beautiful

Show 1 more comment

Browser other questions tagged java recursion

You are not signed in. Login or sign up in order to post.