Leaving recurrence summation in terms of $k$, $\sum_{i=0}^{k-1}\frac{3^i\sqrt{\frac n{3^i}}}{\log\frac n{3^i}}$

Question

I have an exercise where I need to use the substitution method to solve the following recurrence and determine their corresponding complexity. $$t(n)=3t(n/3) + \frac{\sqrt n}{\log n}$$ After some iterations, I got the following pattern. $$t(n)=t\left(\frac{n}{3^k}\right)+\sum_{i=0}^{k-1}\frac{3^i\sqrt{n/3^i}}{\log n/3^i}$$

Honestly I do not know what kind of approach I could use to solve the summation, and leave everything in terms of $k$.

Answer 1

$$ t(2^{\log_2 n}) = 3 t\left(2^{\log_2\left(\frac u2\right)}\right)+\frac{\sqrt n}{\ln n} $$

now calling $T(u) = t(2^u)$ with $u = \log_2 n$ we follow with

$$ T(u) = 3T(u-1) + \frac{2^{\frac u2}}{u\ln 2} $$

This is a linear recurrence with solution $T(u) = T_h(u) + T_p(u)$

$$ \begin{cases} T_h(u) = 3T_h(u-1) \\ T_p(u) = 3T_p(u-1) + \frac{2^{\frac u2}}{u\ln 2} \end{cases} $$

For the homogeneous we have

$$ T_h(u) = C_0 3^u $$

and now making $T_p(u) = C_0(u) 3^u$ and substituting we have

$$ C_0(u)-C_0(u-1) = 3^{-u}\frac{2^{\frac u2}}{u\ln 2} = \frac{1}{\lambda}\frac{\alpha^u}{u} $$

with $\alpha = \frac{\sqrt 2}{3} < 1$ and $\lambda = \ln 2$

so we have

$$ C_0(u) = \frac{1}{\lambda}\sum_{k=1}^{u}\frac{\alpha^k}{k} $$

and then

$$ T(u) = \left(C_0+\frac{1}{\lambda}\sum_{k=1}^{u}\frac{\alpha^k}{k}\right)3^u $$

hence

$$ t(n) = \left(C_0 + \frac{1}{\ln 2}\sum_{k=1}^{\log_2 n}\frac{\alpha^k}{k}\right)3^{\log_2 n} $$

Answer 2

Hint 1. As regards the asymptotic analysis (complexity?), you may use the Master Theorem. Then $c_{crit}=\log_2(3)\approx 1.58$ and $f(n)=\frac{n^{1/2}}{\log(n)}\leq n^{1/2}$. What about $T(n)$?

Hint 2. Note that $$t(2^n)=3^nt(1)+\sum_{k=0}^{n-1}\frac{3^k\sqrt{2^{n-k}}}{\log (2^{n-k})} =3^nt(1)+3^n\sum_{k=1}^{n}\frac{(\sqrt{2}/3)^k}{k\log (2)}\sim C\cdot 3^n$$ because the series $\sum_{k=1}^{n}\frac{(\sqrt{2}/3)^k}{k\log (2)}$ is convergent (note that $\sqrt{2}/3<1$).