I cannot understand the end of Karatsuba algorithms running time proof. Initially we have formula $$T(n) = 3T(\frac{n}{2}) + rn$$ if n > 1 $$T(n) = r $$ if n = 1 , where r is a constant.

We assumed that $n=2^k$

$$T(2^k) = 3T(2^{k-1}) + r2^k$$ Then we recursively proceeded up to base case. In the end we got $$= 3^kr + 2^kr * \frac{\frac {3}{2} ^ k - 1}{\frac{3}{2} - 1}$$

The next lines of proof I did not understand: $$T(n) <= d3^k$$ d is constant $$n = 2^k$$ $$3^k = x$$ $$log_3x = k = log_2n = \frac{log_3n}{log_32}$$ $$log_3x = log_3n^{1.59}$$ $$x = n^{1.59}$$

Can someone please explain how we got $\frac{log_3n}{log_32}$ and $log_3x = log_3n^{1.59}$

Thank you!


1 Answer 1


$n = 2^k$ by multiplying with $\log_2x$ in both sides we have :

$\log_2xn= \log_2x2^k$


similarly $k=\log_3x$

this might be helpful to understand the properties of logarithms:



You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .