Reccurence solution no using Master Theorem that $T(n)=3T(n/3)+n/\log n, T(1)=1$

Question

I try to solve $T(n)=3T(n/3)+n/\log n, T(1)=1$ recurrence relation without using the Master Theorem. I get the following,

$$T(3^k)=3T(3^{k-1})+\frac{3^k}{log(3^k)}$$

I don't know parameter translation very well, for example, by saying $T(3^k)=S(k)$. However, I try to do the following conversion, but I can't go on from there forward. I don't know what the blue part is going to be.

$$S(k)=3S(k-1)+\color{blue}{\frac{3^k}{log(3^k)}}$$

Can it also be solved by not making use of parameter translation?

It is not homework or assignment, but just to enjoy and learn. I'm toying with them as my hobby.

Answer 1

You have reached the point $$ S(k)=\color{red}{3}\cdot S(k-1)+\color{blue}{\frac{3^k}{k \log(3)}} \tag{1} $$ Almost there! Now set $R(k) = \frac{S(k)}{3^k}$ to get rid of that annoying factor $\color{red}{3}$: dividing (1) by $3^k$ on each side, you get $$ R(k)=R(k-1)+\frac{1}{k \log(3)} \tag{2} $$ which you should be able to solve.

Hint:

Essentially, summing from $k=1$ to $K$ on both sides will be give a telescoping series, and you'll end up with $R(K) = R(0) + \frac{1}{\log 3} \sum_{k=1}^K \frac{1}{k}$, and then remember that that last sum is the Harmonic number, which is $\Theta(\log K)$.

Once you have the asymptotics of $R(k)$, you can get those of $S(k)$ (multiply by $3^k$), then finally of $T(n)$.

Answer 2

First, notice that $\log 3^k$ is $k \log 3$, so the recurrence becomes

$$S(k) = 3S(k-1) + \dfrac{3^k}{k\log 3}$$

Expand $S(k-1)$:

$$S(k) = 3\left(3S(k-2) + \dfrac{3^{k-1}}{(k-1)\log3}\right) + \dfrac{3^k}{k\log 3} =$$ $$= 9S(k-2) + \dfrac{3^k}{(k-1)\log 3} + \dfrac{3^k}{k\log 3} =$$ $$=9S(k-2) + \dfrac{3^k}{\log 3}\left(\dfrac{1}{k} + \dfrac{1}{k-1}\right)$$

Do you see the pattern?

Keep going to obtain

$$S(n) = 3^kS(0) + \dfrac{3^k}{\log 3}\sum\limits_{n=1}^{k}\dfrac{1}{n}$$,

where the sum is approximately $\ln k$

Answer 3

With $a > 0$

$$ S(k)=a S(k-1) + \frac{a^k}{k} $$

It is a linear recurrence then it has the linearity benefits:

$$ S(k) = S_h(k)+S_p(k) $$

where

$$ \cases{ S_h(k)-a S_h(k-1) = 0\\ S_p(k)-a S_p(k-1) = \frac{a^k}{k} } $$

The homogeneous has as solution

$$ S_h(k) = c_0 a^k $$

and a particular solution can be obtained by assuming $S_p(k) = c_0(k)a^k$ so after substitution we have

$$ c_0(k) a^k - a c_0(k-1)a^{k-1} = \frac{a^k}{k} $$

or

$$ c_0(k)-c_0(k-1) = \frac 1k $$

then $c_0(k) = \sum_{i=1}^k\frac 1i$ hence

$$ S_p(k) = a^k\sum_{i=1}^k\frac 1i $$

and

$$ S(k) = \left(c_0+\sum_{i=1}^k\frac 1i\right)a^k $$

Now going backwards, as $k = \log_a n$ we have

$$ T(n) = \left(c_0+\sum_{i=1}^{\log_a n}\frac 1i\right)n $$

then

$$ T(n) = \mathcal{O}(n) $$