Как рассчитать сложность рекурсивного алгоритма в нотации Big O?

Question

Рекурсивный алгоритм имеет сложность: Вт (п) = 2W (п/2) + Θ (п)

Мой раствор или догадка О (п).

Как решить такую ​​сложность?

Answer 1

Подобные ситуации покрыты Master Theorem. Кроме того, легко видеть, непосредственно:

W(n) = 2 W(n/2) + Theta(n) 
    = 2(2 W(n/4) + Theta(n/2)) + Theta(n) 
    = 4 W(n/4) + 2 Theta(n) 

Так с каждым шагом рекурсии вы получите другой Theta (п) и глубины рекурсии журнала п. Таким образом, общее усилие O (n log n).