CODEWITHSUNDEEP
javatime-complexitypalindrome
mahesh87
mahesh87

Reputation: 45

Time Complexity of the Palindrome recursive algorithm

What is the time complexity of the below code which checks whether the given input is palindrome or not?

public boolean isPalindromeRecursion(String input, int first, int last) {
    if (input.charAt(first) != input.charAt(last)) {
        return false;
    } else if (first >= last) {
        return true;
    }
    return isPalindromeRecursion(input, first + 1, last - 1);
}

Upvotes: 1

Views: 357

Answers (1)

Giorgi Tsiklauri
Giorgi Tsiklauri

Reputation: 11136

Time complexity of your algorithm, is:

  1. Strictly speaking - O(n/2);
  2. Speaking in the Asymptotic Analysis language - O(n), as the constant factors are disregarded when we use Big O analysis, and it's good that they are disregarded.

Upvotes: 4

Related Questions