Time Complexity O() of isPalindrome()

Answer 1

First improvement: you can break once you find a nonmatch, right?

Answer 2

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 3

It is O(N). You are doing N comparisons, where N=s.length(). Each comparison takes O(1) time, as it is a single character comparison.

+3 does not matter, as asymptotic notation only cares about the highest order term.

Answer 4

You can cut the complexity of the function in half by stopping at (i == (s.length() / 2)+1) Not relevant in BigO terms, still a pretty decent gain.

Answer 5

big-o complexity is always without costants (since them, for N->oo, are unimportant). So your time complexity is simply O(n)

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

this is not your job, the JIT compiler will handle this micro optimization for you

Answer 6

so first of all, what is the method supposed to do?

my guess: determine if a strinig is a palindorome.

quite obviously, you will not be able to get it down under O(N)

O(N+3) == O(N)

the other question is, is it the most efficient solution? maybe not.

room for improvement: 1) cut it in half. you check all characters two times.(like Michiel Buddingh suggested.)

2) obtain the char array beforehand, that spares you some index checks that occur inside chatAt()

all other operations, charAt() length() are O(1) with the standard String implementation.

Answer 7

Assuming the operations in your loop can be executed in constant time, the complexity is O(N). Since "Big-O" notation measures growth, not pure speed, constant factors can be disregarded. This leaves us with the conclusion that O(N+3) is equal to O(N).

Answer 8

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 9

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.

is - like all other proposed solutions still O(N)

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 to 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 10

Since everybody is hung up on for-loops here :), I will present another approach. Why not use StringBuilder, and reverse the second half to compare it with the first half? There is a special case when the string has a odd length, but the middle character can be disregarded since it's always a palindrome in itself.

boolean isPalindrome(String str) {
    int halfLength = str.length() / 2;
    int rightPartStart = str.length() % 2 == 1 ? halfLength + 1 : halfLength;
    StringBuilder sb = new StringBuilder(str.substring(rightPartStart));
    return str.substring(0, halfLength).equals(sb.reverse().toString());
}

Answer 11

First, there cannot be a single-thread solution for this problem where the "worst-case" complexity is better than O(N) for arbitrary input strings. Simply put, any algorithm must look at every character in the string in the worst case. In theory you can improve on O(N) using hardware parallelism; i.e. have an indefinitely scalable number of processors working on different portions of the string. In practice, it would be hard to achieve any speed-up at all. The cost of sending the input string (or relevant parts) to each processor is going be 'O(N)', unless there is some solution that I don't know about.

Second, as you can see O(N) behaviour isn't the final answer. You also need to consider the multiplicative constant as N -> infinity, and the lesser terms for smaller values of N.

Third, @dfa says that it is not your business to micro-optimize. He's on the right track, but I don't think it is quite as clear cut as that. IMO, it is a waste of time micro-optimizing unless 1) your application really needs to run as fast as possible, and 2) your profiling of the application shows that this particular calculation really is a significant bottle-neck.

Finally, a micro-optimization that makes a program faster for one particular hardware platform / JIT compiler, may make it slower for another one. Complex micro-optimized code is harder for a JIT compiler to generate efficient code for. And if you use reflection to access the internals of (say) the String class, your code might actually fail on some platforms. (Nothing in the Java Class Library specification says that a String has a private field called "value" that is a char[]!!!)

Answer 12

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).