Рекурсивная Сложность

Question

Не могли бы вы помочь мне понять сложность этого алгоритма?

int geometric(float *table, int l, int r)
{
    if (r < l) return 1;
    if (r == l) return table[r];

    else { 
        quicksort(table, l, r);
        return sqrt(geometric(table, l, (l+r)/2) * geometric(table, (l+r)/2+1, r));
    }
}

Где quicksort имеет нормальную временную сложность O(N log N).

Можете ли вы сказать мне, какой изэти параметры верны в отношении сложности времени рекурсивной функции geometric?

Answer 1

Если мы применим основную теорему к ней, это дает,

На самом деле, я предполагаю, что Потому float*, фрагмент кода написан на C с math.h.Итак, сложность AFAIK в C sqrt() равна Theta(n), поэтому она должна быть Cn = 2C(n/2) + n^2*lgn.

В противном случае, если это Theta(lgn),

, где T - функция geometric.

Почти всегда на каждом шаге предоставляется sqrt().

Тем не менее, если мы примем сложность sqrt() как Theta(1), результат указывает на параметр A.

---

En passant, опция D уже конфликтует сама с собой, так как дает