Как решить итеративное уравнение подстановки?

Question

Итак, я борюсь с вопросом, мне нужно найти временную сложность этого уравнения с помощью итеративной подстановки. Теперь я понимаю, как расширить уравнение, однако я не знаю, как найти временную сложность, используя его. Я знаю, что ответ o(n^log2 3).

T(n) = 3T(n/2) + O(n)

Я подробно рассказал о том, что мне делать дальше?

3^3T(n/2^3) + 3^2(n/2^2) + 3n/2 + n

Что мне делать дальше, чтобы получить ответ из o(n^log2 3)?
Может кто-нибудь, пожалуйста, объясните мне это шаг за шагом?

Answer 1

Это можно решить так:

T(n) = 3T(n/2) + O(n)

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

     = 3^2(T(n/4)) + O(n)

     = 3^4(T(n/8)) + O(n)

Примечание O(n/4) + O(n/2) + O(n) по-прежнему O(n)

let n = 2^k

then T(n) = 3^(k-1) + O(n)

          = 3^(log(n) - 1 ) + O(n) // log(n) is log (n) to base 2

          = O( n^log(3) ) because n^log(3) > n