java - 嵌套循环递归的 Big-O 复杂性

Question

准备考试时我在一次旧考试中遇到了这个问题:

这个函数的最坏情况/大O复杂度是多少:

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

(是的，代码没有任何意义，但这正是它的编写方式)。

令我困惑的是，每个递归级别 n 的总大小都会加倍，但建议的答案(最终结果为 O(log n * n^2) )忽略了该部分。我是不是理解错了？

编辑:用语法正确(但仍然无意义)的代码替换半伪代码。

Answer 1

如果解决这个递归关系，您就能够确定复杂性。

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

与

T(1) = c