1
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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

$\endgroup$
3
  • $\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$
    – Nathaniel
    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
0
$\begingroup$

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}. $$

$\endgroup$
0
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.