Сложность рекурсии

Question

Что будет Big-O следующего кода:

int f(int n)
{
int i, x;
if (n < 0)

return 1;
x = 0;
for (i = 0; i < n; ++i)

x = x + i;
return x + f(n - 2);
}

Интересно, как записать это в стандартной форме T (n), чтобы использовать последнюю теорему Мастера. Будет ли это что-то вроде: T (n) = n / 2T (n-2)?

Answer 1

Не бери в голову, что там внутри функции, сначала просто посмотри рекурсивный вызов ...

проблема размера n теперь стала проблемой размера n / 2.

сколько раз вызывается эта рекурсивная функция?n раз, поскольку цикл for внутри функции выполняется n раз.

, следовательно, T (n) = n * T (n / 2).

Answer 2

Если быть точным, то форма T (n) = (n + 2) T (n-2).

Но для простоты вы можете приблизить ее к T (n) = nT (n-2)) поскольку Big-O будет зависеть только от этого термина