CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Nhat Dinh
Nhat Dinh

Reputation: 3447

How to calculate algorithm time complex

I am trying to multiple two big integer with Karatsuba algorithm. I known that O(n) is time complexity and T(n) is worst-case time complexity.

Can some one please explain why: 

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

And 

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

Upvotes: 1

Views: 178

Answers (1)

xenteros
xenteros

Reputation: 15852

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

According to the Master theorem:

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

and

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

is 

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

so you can round it to 1.590.

Upvotes: 1

Related Questions