Time complexity O() of isPalindrome()

Question

I have this method, isPalindrome(), and I am trying to find the time complexity of it, and also rewrite the code more efficiently.

boolean isPalindrome(String s) {
    boolean bP = true;
    for(int i=0; i<s.length(); i++) {
        if(s.charAt(i) != s.charAt(s.length()-i-1)) {
            bP = false;
        }
    }
    return bP;
}

Now I know this code checks the string's characters to see whether it is the same as the one before it and if it is then it doesn't change bP.

And I think I know that the operations are s.length(), s.charAt(i) and s.charAt(s.length()-i-!)).

Making the time-complexity O(N + 3), I think? This correct, if not what is it and how is that figured out.

Also to make this more efficient, would it be good to store the character in temporary strings?

Answer 1

It's just O(N).

Saying O(N+3) isn't really meaningful - constant factors are ignored.

You could make it quicker by breaking out when it finds a mismatch:

bP = false;
break;

(Not that that changes the fact that it's O(N), but it will speed it up in most cases.)

This isn't true:

this code checks the string's characters to see whether it is the same as the one before it

It checks that the characters at the start match the ones at end, so in other words it's a naive palindrome checker.

Another speedup would to loop until s.length()/2 - otherwise you're doing all the comparisons twice for a string that is a palindrome.

Answer 2

The given code appears to be checking if a string is a palindrome by checking if character "N" is the same as character "length-N". As already mentioned, you can increase the efficiency by

• only checking the first half
• breaking out (return false) as soon as you find a non-match

To those suggestions, I'd add

• don't recalculate s.length() repeatedly every time through the loop since it doesn't change.

Given all that:

boolean isP(String s) {
  int l = s.length();
  int l2 = l/2;
  int j = l - 1;
  for(int i=0; i<l2; i++) {
    if(s.charAt(i) != s.charAt(j)) {
        return false;
    }
    j--;
  }
  return true;
}

Answer 3

This is most likely the most efficient implementation in Java:

    public static boolean isP(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < (chars.length / 2); i++) {
            if (chars[i] != chars[(chars.length - i - 1)])
                return false;
        }
        return true;
    }

Benefits:

• Returns on first sight of difference.
• Uses direct char[] access to avoid aboundary checks done in charAt
• Only iterates half the string, as opposed the full string.

It is, like all other proposed solutions, still O(N).

I just measured the times fo the presented solutions for a really big string (times in nanoseconds):

 Aran:           32244042
 Andreas:        60787894
 Paul Tomblin:   18387532

First, the measurements above were done with the client VM. Thus the calculation i < (chars.length / 2) was not inlined as a constant. Using the -server Vm parameter gave a much better result:

 Aran:           18756295
 Andreas:        15048560
 Paul Tomblin:   17187100

To drive it a bit extreme:

---

A word of warning first: DO NOT USE THIS CODE IN ANY PROGRAM YOU INTEND TO USE/SHIP.

---

It contains hidden bugs and does not obey the Java API and has not error handling, as pointed out in the comments. It serves purely to demonstrate the theoretical performance improvements obtainable by dirty tricks.

There is some overhead when copying the array from the string, because the string class internally makes a defensive copy.

If we obtain the original char[] from the string directly, we can squeeze out a bit of performance, at the cost of using reflection and unsave operations on the string. This gets us another 20% performance.

public static boolean isPReflect(String s) {
    char[] chars = null;
    try {
        final Field f = s.getClass().getDeclaredField("value");
        f.setAccessible(true);
        chars = (char[]) f.get(s);
    }
    catch (IllegalAccessException e) {
    }
    catch (NoSuchFieldException e) {
    }

    final int lenToMiddle = chars.length / 2;
    for (int i = 0; i < lenToMiddle; i++) {
        if (chars[i] != chars[(chars.length - i - 1)]) 
            return false;
    }
    return true;
}

Times:

 Aran:           18756295
 Andreas1:       15048560
 Andreas2:       12094554
 Paul Tomblin:   17187100

Answer 4

Here’s another solution with two opposite pointers:

boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
        ++i;
        --j;
    }
    return i >= j;
}

The complexity is again O(n).

Going a little more into details: Let’s say every operation costs 1 unit. Comparisons, assignments, arithmetic operations, function calls each cost 1 unit. So a call of isPalindrome costs at worst case (s is a palindrome) takes for example:

  4 + n/2 · (3 + 4) + 1
= 5 + n/2 · 7
= 5 + 7/2 · n

And since the constant factor (here 5 + 7/2) is omitted, we end up with 5 + 7/2 · n ∈ O(n).