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!
$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