Return to Question

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, 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 n \right) + f(n). \end{align*}

I've tried other guesses and have gotten similarly stuck. Any 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.

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.

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, but I get stuck regardless of my choice. If $T(n) = O(n)$, it must be true that \begin{align*} T(n)&\leq c d_1 n + c d_2 n + \dots + cd_k n + f(n)\\ &= c(d_1 n + d_2 n + \dots d_k n) + f(n) \\ \end{align*} After which point I don't know how to proceed since I have a constraint on $\sum f(d_i)$, which I'm not seeing how to use here.

If $T(n) = \lg n $ then it must be true that

\begin{align*} T(n) &\leq c \lg (d_1 n) + c \lg(d_2 n) + \dots + c \lg(d_k n) + f(n) \\ &=c (\lg d_1 + \lg n + \lg d_2 + \lg n + \dots + \lg d_k + \lg n) + f(n) \\ &=c \left( \left(\sum_{i=1}^{k} \lg (d_i)\right) + k \lg n \right) + f(n). \end{align*}

I've tried other guesses and have gotten similarly stuck. Any pointers on how to proceed? I presume it involves incorporating the constraints on $\sum f(d_i)$, but right now I am not seeing how to incorporate them.

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, 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 n \right) + f(n). \end{align*}

I've tried other guesses and have gotten similarly stuck. Any 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.