CODEWITHSUNDEEP
javaarrayscharequalstime-complexity
Brian
Brian

Reputation: 7326

Time complexity of Arrays.equals()

I have two char arrays generated from two strings.I would like to determine whether the arrays are equals.

str1Array = str1.toCharArray();
str2Array = str2.toCharArray();

My understanding is that str1Array.equals(str2Array) will only return true when the array objects are the same object in memory. If I want to check whether each of the indices are the same, I should use Arrays.equals(str1Array, str2Array)

I am wondering about the complexity of this equals method.

I assume it cannot be O(1) because it is not able to evaluate the content equality of the array objects without checking equality for each index. My guess is that it is O(n) where n corresponds to the min(str1Array.length, str2Array.length)

Can anyone verify this or comment otherwise?

Upvotes: 9

Views: 7906

Answers (1)

Anubian Noob
Anubian Noob

Reputation: 13596

Well, let's look at the source code:

public static boolean equals(Object[] a, Object[] a2) {
    if (a==a2)
        return true;
    if (a==null || a2==null)
        return false;

    int length = a.length;
    if (a2.length != length)
        return false;

    for (int i=0; i<length; i++) {
        Object o1 = a[i];
        Object o2 = a2[i];
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }

    return true;
}

(It's about the same for the other variations of the method).

As we can see, it's iterating through the array. So it has a worst-case complexity of O(n), where n is the length of the arrays compared. (If the arrays are different sizes, then it exits immediately, making it O(1)).

However, it doesn't always take that long. It does have some preconditions for equality, a null check, and a length check. It also exits as soon as a match is found, so it could take a lot less time.

Upvotes: 14

Related Questions