CODEWITHSUNDEEP
javastringbig-o
user1054740
user1054740

Reputation: 523

what is the time complexity of .equals in java for 2 strings?

I was wondering what the time complexity (big O) of the .equals operator in Java was for two strings.

Basically, if I did stringOne.equals(stringTwo) how well does this perform?

Thanks.

Upvotes: 18

Views: 13991

Answers (3)

Yeikel
Yeikel

Reputation: 935

To add to the excellent answers , we can see it looking at the code : 

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

Best case : O(1)

Worst case : O(n)

Upvotes: 1

mikera
mikera

Reputation: 106401

The other answers here are over-simplistic.

In general, proving that two different Strings are equal is O(n) because you may have to compare each character.

However this is only a worst-case: there are many shortcuts that mean that the equals() method can perform much better than this in the average / typical cases:

  • It's O(1) if the Strings are identical: they are the same object so equal by definition so the result is true
  • It's O(1) if you are able to check pre-computed hashcodes, which can prove that two Strings are not equal (obviously, it can't help prove that two Strings are equals because many Strings hash to the same hashcode).
  • It's O(1) if the Strings are of different lengths (they can't possibly be equal, so the result is false)
  • You only need to detect one different character to prove that Strings are not equal. So for randomly distributed Strings, it is actually average O(1) time to compare two Strings. If your Strings aren't completely random, then the result may be anywhere between O(1) and O(n) depending on the data distribution.

As you can see, the exact performance depends on the distribution of the data.

Apart from that: this is implementation dependent so exact performance characteristics will depend on the version of Java used. However, to my knowledge, all the current main Java implementations do the optimisations listed above so you can expect equals() performance on Strings to be pretty fast.

A final trick: If you use String interning then all Strings that are equal will be mapped to the same object instance. Then you can use the extremely fast == check for object identity in place of equals(), which is guaranteed to be O(1). This approach has downsides (you may need to intern a lot of Strings, causing memory issues, and you need to strictly remember to intern any Strings that you plan to use with this scheme) but it is extremely useful in some situations.

Upvotes: 23

user1596371
user1596371

Reputation:

Worst case is O(n), unless the two strings are the same object in which case it's O(1).

(Although in this case n refers to the number of matching characters in the two strings starting from the first character, not the total length of the string).

Upvotes: 14

Related Questions