# Solve $T(n) = \frac78T(\frac78n) + \frac78n$

The recurrent function $$T(n) = \frac78T\left(\frac78n\right)+\frac78n$$ where $$T(1) = 0$$ and $$n = \left(\frac87\right)^k$$ represents the running time of an algorithm. How can I find a more simple form (depending only on n) of this function? I kept replacing $$T\left(\frac78n\right)$$ and $$T\left(\frac78\times\frac78n\right)$$ etc ... with its value but I don't seem to have any pattern.

You can show that $$\frac78n\leqslant T(n) \leqslant n\sum\limits_{i = 1}^{+\infty}\left(\frac78\right)^i = 7n$$.

• Actually $T(n) \ge \frac{7}{8}n$ doesn't hold, consider $n = 1$ for example. Feb 10, 2022 at 22:03
• Yes, and $T(n) \leqslant 7n$ doesn't hold either if $T(1)$ is big enough. However, the idea is good enough as a hint, ignoring initial conditions, no? Feb 10, 2022 at 22:15
• Sure, though it could be improved (the terms actually decrease twice as fast). Feb 10, 2022 at 22:19

Let $$S(k) = T((8/7)^k)$$. Then $$S(0) = 0$$ and $$S(k+1) = \frac{7}{8} S(k) + \left(\frac{8}{7}\right)^k.$$ Unrolling, we get \begin{align} S(k) &= \left(\frac{8}{7}\right)^{k-1} + \frac{7}{8} S(k-1) \\ &= \left(\frac{8}{7}\right)^{k-1} + \frac{7}{8} \left(\frac{8}{7}\right)^{k-2} + \left(\frac{7}{8}\right)^2 S(k-2) \\ &= \cdots \\ &= \left(\frac{8}{7}\right)^{k-1} + \frac{7}{8} \left(\frac{8}{7}\right)^{k-2} + \left(\frac{7}{8}\right)^2 \left(\frac{8}{7}\right)^{k-3} + \cdots + \left(\frac{7}{8}\right)^k S(0) \\ &= \left(\frac{8}{7}\right)^{k-1} + \frac{7}{8} \left(\frac{8}{7}\right)^{k-2} + \left(\frac{7}{8}\right)^2 \left(\frac{8}{7}\right)^{k-3} + \cdots + \left(\frac{7}{8}\right)^{k-1} \\ &= \left(\frac{8}{7}\right)^{k-1} \left[ 1 + \left(\frac{7}{8}\right)^2 + \cdots + \left(\frac{7}{8}\right)^{2(k-1)} \right] \\ &= \left(\frac{8}{7}\right)^{k-1} \frac{1-\left(\frac{7}{8}\right)^{2k}}{1-\left(\frac{7}{8}\right)^2} \\ &= \frac{64}{15} \left(\frac{8}{7}\right)^{k-1} - \frac{64}{15} \left(\frac{7}{8}\right)^{k+1}. \end{align} If $$n = (8/7)^k$$, then this gives $$T(n) = \frac{56}{15} n - \frac{56}{15} \frac{1}{n}.$$

Regarding the recurrence

$$T\left( n\right) = c T\left(\frac{a}{b}n \right) + f(n)$$

with $$\{a,b,n\}\in \mathbb{N}^+$$, $$a,b$$ relative primes, $$c\in \mathbb{R}$$. Considering now $$n = b^m q$$ with $$\{q,m\}\in \mathbb{N}^+$$ and $$q \not|\; b$$, the path from $$n = b^m q$$ to extinction is

$$\{b^m q, b^{m-1}a q,\cdots, b^{m-k}a^k q,\cdots,b a^{m-1}q,a^m q\}$$

so calling now $$T(a^m q)= T_{q_0}$$ we have

$$T(b^m q) = c^m T_{q_0}+\sum_{k=1}^{k=m}c^{m-k}f(a^{m-k}b^k q)$$

now making $$\lambda=\frac ab$$ and with $$T_{q_0}=0$$ analyzing

$$\lim_{n\to\infty}\frac{T(n)}{n}=\lim_{m\to\infty}\frac{T(b^mq)}{b^m q} = \lim_{m\to\infty}\frac{1-\lambda^{2m}}{1-\lambda^2}\lambda$$

but here $$\lambda=\frac ab\lt 1$$ so

$$\lim_{n\to\infty}\frac{T(n)}{n}=\frac{\lambda}{1-\lambda^2} = \frac{56}{15}$$