Вычислить временную сложность рекуррентного отношения при повторном замещении

Question

Путем повторной замены решите следующее рекуррентное соотношение-

f (n) = 4f (n / 2) + g (n) с g (n) ∈ θ (n) и f (1) ∈ θ (1)

Answer 1

Просто сделай это! f(n) = 4 (4f(n/4) + g(n/2)) + g(n) = 4^2 f(n/2^2) + 4 g(n/2) + g(n) = 4^2(4f(n/2^3) + g(n/2^2)) + 4 g(n/2) + g(n) = 4^3 f(n/2^3) + 4^2 g(n/2^2) + 4 g(n/2) + g(n). Теперь мы можем обобщить это по индукции: f(n) = sum_{i = 0}^{log(n)} 4^i g(n/2^i). Как g(n) = Theta(n), пусть заменит g(n) на n. У нас будет, f(n) = sum_{i = 0}^{log(n)} 4^i * n/2^i = sum_{i = 0}^{log(n)} 2^i * n = n * sum_{i = 0}^{log(n)} 2^i = n * (1 + 2 + 2^2 + ... + 2^log(n)) = n * (2^(log(n)+1)-1) = n * (2n - 1) = Theta(n^2).

Кроме того, вы можете использовать основную теорему для ее решения.