I'm having trouble deciphering what this recurrence relation is: $$T(n) = T(n^\frac13) + \log n$$ when I try to expand it out I get: $T(n) = T(n^\frac1{3^k}) + k\times\log n $
my problem is breaking down or converting what the big oh notation is, I've seen examples for substituting $n=2^k$ but I don't think that works here. and solving $n^{\frac1{3^k}}=0$ doesn't look right to me.
NOTE
This answer is faulty! Sorry for that! See comment section.
You can write $$ T(n^3)=T(n)+3\log n $$ and then substitute $n=2^k$ to have $$ T(2^{3k})=T(2^k)+3k\log 2 $$ and finally substitute $k=3^m$ to have $$ T\left(2^{(3^{m+1})}\right)=T\left(2^{(3^m)}\right)+3^{m+1}\log 2 $$ From which we are able to deduce recursively that $$ \begin{align} T\left(2^{(3^{m+1})}\right)&=T(2)+(3^{m+1}+3^m+...+9+3)\log 2\\ &=T(2)+\frac{3^{m+2}-3}{3-1}\cdot\log(2) \end{align} $$ and so for large values of $n=2^k=2^{(3^{m+1})}$ corresponding to $m=\log_2(\log_3(n))-1$ or equivalently $m=\log_3(\log_3(n)^{1/\log_3(2)})-1$ we have $$ T(n)\approx \frac{3^{m+2}}2\cdot\log 2=\frac{3}{2}\cdot \log_3(n)^{1/\log_3(2)}\cdot\log 2 $$ Since $1/\log_3(2)\approx 1.5849625$ it appears that we must roughly have $$ T(n)\in\Theta((\log n)^{1.5849625}) $$ so this is slightly faster than mere logarithmic growth - if I am not mistaken.