Using substitution method solve the recurrence $T(n) = 3T(\frac{n}{3}) + \frac{n}{(\log n)}$

Question

I try to do it as seen in this answer but since my log is base 3 it doesn´t turn into i

image of my incomplete attempt to find complexity

if my n=3^k then my sum´s division is 0, so I must be doing something wtong but idk what.

Answer 1

With $n=3^m$ and assuming $\log n \equiv \log_3 n$

$$ T\left(3^m\right) = 3T\left(3^{m-1}\right) + \frac{3^m}{m} $$

making $\mathcal{T}\left(\cdot\right)= T\left(3^{(\cdot)}\right)$ we follow with

$$ \mathcal{T}\left(m\right)=3\mathcal{T}\left(m-1\right)+\frac{3^m}{m} $$

This is a linear recurrence with solution to the homogeneous

$$ \mathcal{T}_h\left(m\right)=c_03^m $$

choosing as a particular solution $\mathcal{T}_p(m)= c_m3^m$ after substitution we have

$$ c_m3^m=3c_{m-1}3^{m-1}+\frac{3^m}{m} $$

so

$$ c_m = c_{m-1}+\frac 1m $$

and

$$ c_m = H_m $$

and finally

$$ \mathcal{T}\left(m\right)=(c_0+H_m) 3^m $$

but $m = \log_3 n$ hence

$$ T(n) = n(c_0+H_{\log_3 n}) $$