CODEWITHSUNDEEP
javaarraysruntimeequals
cinnamon toast
cinnamon toast

Reputation: 177

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

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.

Upvotes: 9

Views: 2034

Answers (4)

Peter Lawrey
Peter Lawrey

Reputation: 533780

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.

Upvotes: 8

assylias
assylias

Reputation: 328785

The javadoc states: two arrays are equal if they contain the same elements in the same order. So it is clear that this is going to be an O(n) operation as it will need to loop over all the items (at least if they are all equal).

The default equals (i.e. Object#equals) is an O(1) operation, it is a simple reference comparison:

for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true)

Upvotes: 0

Thilo
Thilo

Reputation: 262794

It first checks the length, and if equal, loops over all elements and calls equals on them.

So, if you want to ignore the cost of the individual equals, yes, that would be O(n). But if the entries are Strings, for example, it will also get longer as the Strings get longer, not just as they get more (because the comparisons themselves are O(m) as well).

Upvotes: 6

Eng.Fouad
Eng.Fouad

Reputation: 117665

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;
}

Upvotes: 12

Related Questions