Time complexity of Arrays.deepEquals() in Java

Question

I'm trying to figure out the time complexity for the java.util.Arrays deepEquals() method.

I could understand from the source code that equals() method runs in O(n) time, but it's not really that clear to deduce the time complexity from the deepEquals() method. It runs in a loop, but also calls the deepEquals0 method, which should check the elements' equal recursively? So what would here be the worst case scenario?

Here's the snippet which was taken from the java.util.Arrays class:

public static boolean deepEquals(Object[] a1, Object[] a2) {
    if (a1 == a2)
        return true;
    if (a1 == null || a2==null)
        return false;
    int length = a1.length;
    if (a2.length != length)
        return false;

    for (int i = 0; i < length; i++) {
        Object e1 = a1[i];
        Object e2 = a2[i];

        if (e1 == e2)
            continue;
        if (e1 == null)
            return false;

        // Figure out whether the two elements are equal
        boolean eq = deepEquals0(e1, e2);

        if (!eq)
            return false;
    }
    return true;
}

static boolean deepEquals0(Object e1, Object e2) {
    assert e1 != null;
    boolean eq;
    if (e1 instanceof Object[] && e2 instanceof Object[])
        eq = deepEquals ((Object[]) e1, (Object[]) e2);
    else if (e1 instanceof byte[] && e2 instanceof byte[])
        eq = equals((byte[]) e1, (byte[]) e2);
    else if (e1 instanceof short[] && e2 instanceof short[])
        eq = equals((short[]) e1, (short[]) e2);
    else if (e1 instanceof int[] && e2 instanceof int[])
        eq = equals((int[]) e1, (int[]) e2);
    else if (e1 instanceof long[] && e2 instanceof long[])
        eq = equals((long[]) e1, (long[]) e2);
    else if (e1 instanceof char[] && e2 instanceof char[])
        eq = equals((char[]) e1, (char[]) e2);
    else if (e1 instanceof float[] && e2 instanceof float[])
        eq = equals((float[]) e1, (float[]) e2);
    else if (e1 instanceof double[] && e2 instanceof double[])
        eq = equals((double[]) e1, (double[]) e2);
    else if (e1 instanceof boolean[] && e2 instanceof boolean[])
        eq = equals((boolean[]) e1, (boolean[]) e2);
    else
        eq = e1.equals(e2);
    return eq;
}

Thanks in advance.

Answer 1

The method runs linear on the total amount of elements. If we denote that by n, it is O(n).

Sounds better than it is though, imagine you have a nested array int[][][] like:

{                     // int[][][]
    { 1, 2, 3 },      // int[]
    { 4, 5 },         // int[]
    {                 // int[][]
        { 6, 7, 8 },  // int[]
        { 9 }         // int[]
    }
}

Then we have 9 int values in total. By n I meant those 9 elements, not the 4 for the arrays of the outer structure. It runs linear on that n.

Again, I am not talking about outer.length (which is 4), I am talking about the actual amount of elements if you completely follow down the whole structure, if you flatten it. It is actually impossible to express the complexity in terms of outer.length, as it is completely unrelated. Small example to demonstrate this:

{
    {
        { 1, 2, 3, 4, ..., 1_000_000 }
    }
}

Here, input.length is just 1, but the actual amount of elements is quite huge. You see, it is unrelated.

---

The reason why it calls itself again is because, imagine you have an Object[][][][] (4 dimensions), then you also have to check all of those dimensions. So it really checks all elements.