Big-O complexity of recursion with nested loops

Question

Preparing for exams I came across this question in an old exam:

What is the worst case/big-O complexity of this function:

float foo(float[] A) {
    int n = A.length;
    if (n == 1) return A[0];
    float[] A1 = new float[n/2];
    float[] A2 = new float[n/2];
    float[] A3 = new float[n/2];
    float[] A4 = new float[n/2];

    for (i = 0; i <= (n/2)-1; i++) {
        for (j = 0; j <= (n/2)-1; j++) {
            A1[i] = A[i];
            A2[i] = A[i+j];
            A3[i] = A[n/2+j];
            A4[i] = A[j];
        }
    }

    return foo(A1)
         + foo(A2)
         + foo(A3)
         + foo(A4);
}

(Yes, the code makes no sense, but this is exactly the way it was written).

What's tripping me up is that the total size of n doubles for each recursive level, but the suggested answer(with the end result O(log n * n^2)) ignores that part. Am I misunderstanding things?

Edit: Replaced the semi-pseudocode with syntactically correct(but still nonsensical) code.

Answer 1

Okay, I finally figured it out.

Every time we recurse we do 4 times as many function calls as last time, so if we define the recursion level as m the number of function calls per level is

Every time we recurse we also halve the size of the array, so the amount of work per function call is

At each recursive level the work done in total then is:

In fact 4^m is the same as (2^m)^2:

Thus the amount of work can be written as just n^2:

There are log n recursive levels.

Thus the total amount of work is O(n^2 * log n), and that is because there are 4 recursive calls.

If there were just 2 recursive calls the amount of work at each level would be

which we can't reduce nicely(but turns out to be in O(n^2) if my math is correct).

Answer 2

If you solve this recursive relation, you'd be able to determine the complexity.

T(n) = 4T(n/2) + O(n²)

With

T(1) = c