I feel this is more of a question in the logarithms, but I am confused why this tree reoccurrence
$$T(n) = 3T(2n/3)+1$$
solution is derived from $\log_{3/2}$ rather than $\log_{2/3}$? My thinking about this problem:
$\bullet$ height of this tree is = $\log_{2/3}n$
$\bullet$ The number of nodes is $3^{nodes}= 3^{\log_{2/3}n} = n^{\log_{2/3}3} \approx n^{-2.7}$
$\bullet $ This would make the solution $\Theta(n^{-2.7}) $, but that isn't correct, the correct solution is $\Theta(n^{2.7}) $, which would be obtained using $log_{3/2}$ .
I guess I have a couple of confusion: 1) In the Recurrence part of a recurrence equation the T(n/x) I always assumed would create height $\log_x n$, therefore $T(2n/3)$ would create height $\log_{2/3}n$? 2) I didn't realize the nature of log bases, if the base is a rational fraction then the inverse of the base is produces the same result, but opposite signs. 3)How should I be thinking about the fractional part of the these recurrences equations?
$\endgroup$ 11 Answer
$\begingroup$As
$$ T\left(\left(\frac 23\right)^{\log_{\frac 23}n}\right)=3T\left(\left(\frac 23\right)^{\log_{\frac 23}\frac 23 n}\right)+1 $$
making $\mathcal{T}(\cdot) = T\left(\left(\frac 23\right)^{(\cdot)}\right)$ and $z = \log_{\frac 23}n$ we follow with the recurrence
$$ \mathcal{T}(z) =3\mathcal{T}(z+1)+1 $$
with solution
$$ \mathcal{T}(z) = 3^{1-z}c_0+\frac 12(3^{-z}-1) $$and going backwards with $z = \log_{\frac 23}n$ we get
$$ T(n) = 3^{\log{\frac 23}n+1}c_0 + \frac 12\left(3^{\log{\frac 23}n}-1\right) $$
$\endgroup$
