0
$\begingroup$

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!

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\log_2xn= \log_2x2^k$

$\log_2xn=k$

similarly $k=\log_3x$

this might be helpful to understand the properties of logarithms:

http://www.andrews.edu/~calkins/math/webtexts/numb17.htm

$\endgroup$

You must log in to answer this question.

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