3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Our reference question has an answer about Akra-Bazzi, which solves this recurrence up to $\Theta$. Duplicate? $\endgroup$ – Raphael May 6 '16 at 6:13
  • $\begingroup$ @Raphel Not a duplicate. Akra–Bazzi works best when the function $f(n)$ is explicit. $\endgroup$ – Yuval Filmus May 6 '16 at 8:29
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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