How to compute the running time of Karatsuba Algorithm?

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!

Solution

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)