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

Хорошо, я, наконец, понял это.

Каждый раз, когда мы рекурсия мы делаем в 4 раза больше вызовов функций, как в прошлый раз, поэтому, если мы определим уровень рекурсии, как m количество вызовов функций на уровень

Каждый раз, когда мы рекурсия мы также вдвое сократить размер массива, поэтому объем работы на один вызов функции является

на каждом рекурсивном уровне работы в целом, то есть:

На самом деле 4^m такая же, как (2^m)^2:

Таким образом, объем работы может быть написано как только n^2:

Есть log n рекурсивных уровней.

Таким образом, общий объем работ O(n^2 * log n), и это потому, что есть 4 рекурсивные вызовы.

Если бы только 2 рекурсивных вызовов объем работы на каждом уровне будет

, которые мы не можем уменьшить красиво (но оказывается в O(n^2), если моя математика верна).

Answer 2

Если вы решите это рекурсивное отношение, вы сможете определить сложность.

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

С

T(1) = c