Runtime complexity of String.equals() in Java

Runtime complexity of String.equals() in Java

In theory it depends on the implementation, however I dont think the differences are dramatic, for OpenJDK 7u40-b43, this is the implementation,

public boolean equals(Object anObject) {
    if (this == anObject) {
         return true;
     }
     if (anObject instanceof String) {
         String anotherString = (String) anObject;
         int n = value.length;
         if (n == anotherString.value.length) {
             char v1[] = value;
             char v2[] = anotherString.value;
             int i = 0;
             while (n-- != 0) {
                 if (v1[i] != v2[i])
                         return false;
                 i++;
             }
             return true;
         }
     }
     return false;
 }

As you can see, its O(n), but there are optimizations to make it Ω(1) in any of the these cases:

• the strings are the same object; or
• the thing you checking is not a string; or
• the string lengths are different.

String.equals first compares the reference. If the reference is the same as this, then true is returns. Of if the input param to compare is not String type, false is returned. Then length is compared, if length of the two String are not the same, false is returned. Only in these there case, the complexity is O(1).

Otherwise, the method will compare each character of the two String, which means it has O(n) complexity.

Runtime complexity of String.equals() in Java

You might either look at the source code for String.equals(String arg) ; or run through a debugger in Eclipse where you have attached the source.

My quick check appears to show that the strings are compared character by character.