I have a recurrence relation $T(n) = \left( \sum_{i=1}^{k} T(d_i n) \right) + f(n),ドル where each $ 0 < d_i < 1,ドル $f(x) > 0$ for all $,円 x > 0$ and $f(xy)=f(x) \cdot f(y)$ for $x,y\geq 0$.
I am asked to give an asymptotically tight bound on $T(n)$ if $\sum_{i=1}^{k} f(d_i) < 1$ and if $\sum_{i=1}^k f(d_i) = 1$ using the substitution method, and I am told not to worry about the base case. I am following the substitution method from CLRS section 4.3 and basically means guess an upper bound, and then prove by induction.
I tried several guesses when $\sum f(d_i n) < 1,ドル but I get stuck regardless of my choice. If $T(n) = O(f(n)),ドル it must be true that \begin{align*} T(n)&\leq c f(d_1n) + c f(d_2 n) + \dots + cf(d_k n) + f(n)\\ &= c(f(d_1 n) + f(d_2 n) + \dots f(d_k n)) + f(n) \\ &< c + f(n) & \text{Since} \sum f(d_i n) < 1 \end{align*} Which is false, unless $c < 0,ドル which can't be the case.
If $T(n) = \lg f(n) $ then it must be true that
\begin{align*} T(n) &\leq c \lg (f(d_1 n)) + c \lg(f(d_2 n)) + \dots + c \lg(f(d_k n)) + f(n) \\ &=c [\lg f(d_1) + \lg f(n) + \lg f(d_2) + \lg f(n) + \dots + \lg f(d_k) + \lg f(n)] + f(n) \\ &=c \left( \left(\sum_{i=1}^{k} \lg f(d_i)\right) + k \lg f(n) \right) + f(n). \end{align*} Not sure how to proceed here. When I tried $T(n) = O\left(f(n)^2\right),ドル I got
\begin{align*} T(n) &\leq c \left( \sum_{i=1}^n f(d_i n)^2 \right) + f(n) \\ &< c + f(n) & \text{ since } \sum f(d_i n ) < 1 \implies \sum f(d_i n)^2 < 1 \\ &\leq c f(n)^2 \end{align*} which doesn't seem too tight, but I'm not sure. Any comments or pointers on how to proceed? I presume it involves incorporating the constraints on $\sum f(d_i)$ in some other way, but right now I am not seeing how to do so.
-
$\begingroup$ Our reference question has an answer about Akra-Bazzi, which solves this recurrence up to $\Theta$. Duplicate? $\endgroup$Raphael– Raphael2016年05月06日 06:13:03 +00:00Commented May 6, 2016 at 6:13
-
$\begingroup$ @Raphel Not a duplicate. Akra–Bazzi works best when the function $f(n)$ is explicit. $\endgroup$Yuval Filmus– Yuval Filmus2016年05月06日 08:29:11 +00:00Commented May 6, 2016 at 8:29
1 Answer 1
Form a recursion tree. The root represents $T(n),ドル and has weight $f(n)$. It has $k$ children, the edges are labelled $f(d_1),\ldots,f(d_k),ドル and the children itself have weights $f(d_1)f(n),\ldots,f(d_k)f(n)$; they correspond to $T(d_1n),\ldots,T(d_kn)$. Each child has its own $k$ children, and so on, only we delete nodes corresponding to $T(m)$ for $m < 1$. Note that the weight of each node is $f(n)$ times the weights of all edges from the node to the root. The total running time, assuming a base case around 1ドル,ドル is the sum of all weights in the tree.
When $\sum_{i=1}^k f(d_i) < 1,ドル we can compute the total weight of the infinite tree (without the pruning described above) as $$ f(n) \sum_{t=0}^\infty (f(d_1) + \cdots + f(d_k))^t = \Theta(f(n)); $$ here $(f(d_1) + \cdots + f(d_k))^t f(n)$ is the total weight at level $t$. Thus in this case we have $T(n) = \Theta(f(n))$.
When $\sum_{i=1}^k f(d_i) = 1,ドル each full level contributes $f(n),ドル and each partial level (where some nodes were pruned) contributes at most $f(n)$. There are $\Omega(\log n)$ full levels and $O(f(n))$ full or partial levels, and we conclude that $T(n) = \Theta(f(n)\log n)$.