What is the runtime of equals() in java.util.Arrays?

Question

As title stated, what's the runtime of equals() in java.util.Arrays ?

For example if it's comparing two int[] , does it loop through every element in the array, so O(n)? And for all equals() in individual classes' equals() in java, can we assume that the runtime is always O(n) ?

Thanks.

Answer 1

As title stated, what's the runtime of default equals() in java.util.Arrays?

The default equals could mean Object.equals. The Arrays.equals() is usually what you really want.

For example if it's comparing two int[], does it loop through every element in the array, so O(n)?

yes, thats what the source suggests.

And for all default equals() in java, can we assume that the runtime is always O(n)?

For some collections this is true, but for Tree collections it can be O(n log n). The worst case for HashMap is O(N^2) For non-collections n has no meaning.

Answer 2

Grabbed from the source code (source code is worth 100 words :P):

/**
 * Returns <tt>true</tt> if the two specified arrays of ints are
 * <i>equal</i> to one another.  Two arrays are considered equal if both
 * arrays contain the same number of elements, and all corresponding pairs
 * of elements in the two arrays are equal.  In other words, two arrays
 * are equal if they contain the same elements in the same order.  Also,
 * two array references are considered equal if both are <tt>null</tt>.<p>
 *
 * @param a one array to be tested for equality
 * @param a2 the other array to be tested for equality
 * @return <tt>true</tt> if the two arrays are equal
 */
public static boolean equals(int[] a, int[] 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++)
        if (a[i] != a2[i])
            return false;

    return true;
}