Solving the recurrence $T(n) = 128 \, T\left(\frac{n}{8}\right) + n^{13/3} \, \ln n + \ln^4 n$

52 Views Asked by At

I'm trying to solve the recurrence relation but I keep getting stuck $$T(n) = 128 \, T\left(\frac{n}{8}\right) + n^{13/3} \, \ln n + \ln^4 n$$ I tried doing this $ m = \ln n$ but couldn't get far.

edit :

I was interested in the asymptotic theta of the equation.

using the master theorem I got : $ a= 128 b = 8 , log_8(128) = 3/7 $ if I look at the dominant part of f(n) it's of course $n^\frac73$ so by the second case of master theorem $T(n)= \theta(n\frac73logn)$

sorry for my non existing latex skills :/

1

There are 1 best solutions below

1
On BEST ANSWER

$$T(n)=128\,T(\tfrac n8)+f(n)$$

Basically you want to transform this into $W(p)-W(p-1)=g(p)$ to be able to calculate $W(p)$ as a telescopic sum:

$$W(p)=W(0)+\sum\limits_{i=1}^p g(i)$$

For that we need $2$ things:

  • get rid of the factor $128$

We can set $U(n)=\dfrac{T(n)}{n^a}\implies n^aU(n)=128\dfrac{n^a U(\frac n8)}{8^a}+f(n)$

Therefore we have to get $8^a=128\iff a=\frac 73$

  • transform $n\to p$

We can do that by setting $n=8^p$ and $U(n)=W(p)$ since $U(\frac n8)=W(p-1)$.

With $g(p)=\dfrac{f(n)}{n^{\frac 73}}=\dfrac{f(2^{3p})}{2^{7p}}$


In the end it is not complicated as you'll get various $p^\alpha 2^{\beta p}$ to sum up (which is geometric series, or derivative of geometric series), but very tedious...

Note: if you are interested only in the asymptotic, just calculate the dominant term of $\sum g(i)$.


I have calculated the exact value with CAS using the method presented, here it is:

$\displaystyle\begin{align}T(n)&=\tfrac{64}{63}n^{\tfrac{13}{3}}\ln(n) -\tfrac{64\ln(2)}{1323}n^{\tfrac{13}{3}} +\Big(\tfrac{64\ln(2)}{1323}+\tfrac{23626442880\ln(2)^4}{33038369407}\Big)n^{\tfrac 73}\\\\ &-\tfrac 1{127}\ln(n)^4 -\tfrac{1536\ln(2)}{16129}\ln(n)^3 -\tfrac{891648\ln(2)^2}{2048383}\ln(n)^2 -\tfrac{233584128\ln(2)^3}{260144641}\ln(n)\\\\ &-\tfrac{23626442880\ln(2)^4}{33038369407} \end{align}$

Arranged by decreasing dominant terms.

Asymptotically $T(n)\sim \dfrac{64}{63}n^{\tfrac{13}{3}}\ln(n)$