How to compute the running time of Karatsuba Algorithm?

Question

I know that the formula is T(n)=3T(n/2)+O(n), and using the master method I can get the T(n)=n^(log3) with 2 being the base.

But I still don't know how to get the answer without using master method. Because the result I get from the recursive formula is T(n)=3^(logn) with 2 being the base.

I would be so appreciated if anyone can help me!

Hey @Zoe Lee , Please accept the answer if you feel it has answered your doubts. — adisticated, Oct 09 '16 at 11:41

score 3 · Accepted Answer · answered Oct 09 '16 at 11:33

3

Well That is because you both are correct at the same time.

n^(log3) = 3^(logn)

Proof :

y = 3^log(n)
log(y) = log(n)*log(3)
log(y)/log(n) = log(3)

log<sub>n</sub>y = log(3)

y = n^(log3)

answered Oct 09 '16 at 11:33

adisticated

469
2
10

I can't believe I spend all morning figuring why the result is 3^logn – Zoe Lee Oct 09 '16 at 11:54

How to compute the running time of Karatsuba Algorithm?

1 Answers1