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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
You can show that $\frac78n\leqslant T(n) \leqslant n\sum\limits_{i = 1}^{+\infty}\left(\frac78\right)^i = 7n$.
answered Feb 10, 2022 at 15:16
-
$\begingroup$ Actually $T(n) \ge \frac{7}{8}n$ doesn't hold, consider $n = 1$ for example. $\endgroup$ Feb 10, 2022 at 22:03
-
$\begingroup$ 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? $\endgroup$ Feb 10, 2022 at 22:15
-
$\begingroup$ Sure, though it could be improved (the terms actually decrease twice as fast). $\endgroup$ Feb 10, 2022 at 22:19
$\begingroup$
$\endgroup$
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}. $$
answered Feb 10, 2022 at 22:01
$\begingroup$
$\endgroup$
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} $$
