Как вычислить комплексный алгоритм времени

Question

Я пытаюсь несколько двух больших чисел с алгоритмом Karatsuba. Я знаю, что O(n) - сложная временная сложность, а T(n) - наихудшая временная сложность.

Может кто-нибудь, пожалуйста, объясните почему:

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

И

T(n) = 3T(n/2) + O(n) is O(n^1.59) 

Answer 1

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

Согласно теореме Master:

T(n) is O(n^log_2(4)) = O(n^2) 

и

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

является

T(n) = O(log_2(3)) ~ O(n^1,5849) 

так что вы можете округлить его 1.590.