Can the output value be solved and/or written as Taylor expansion?

Question

imho this is not at all a duplicate, because the other question does not address the "recursive" case $T(d,n) = ....T(d-1,T(d-1,n))....$, which appears to be part of the Taylor expansion of this function. Also I don't know how to write this as a Taylor expansion. If I would, I would still not know how to solve this specific instance.

Consider the following function. Maybe it could be more efficient, but I'm only interested in the output value, not the runtime complexity. All variables are whole numbers.

function branch(currentDepth, maxDepth, n, k) {
    if (currentDepth == maxDepth) {
        return n;
    }
    sum = 0;
    for (i=0; i<=k; i++) {
        tmpN = branch(currentDepth+1, maxDepth, n, i);
        sum += branch(currentDepth+1, maxDepth, tmpN, k-i);
    }
    return sum;
}

For $2 < k << n$ and $2 < d = O(\log n)$, is there a formula in terms of $d$, $k$ and $n$ (either exact, big-O or Theta), that predicts the output for

branch(0, d, n, k);

Will it be exponential in $n$? Can we maybe solve this for small $k$? ($k\le7$).

Application: the output value is a factor of the runtime complexity of a Fixed Parameter algorithm I made up, but I don't think it will beat existing algorithms. However I still wanted this solved.

Answer 1

It is better to use as parameters maxDepth-currentDepth, n, k. Call the resulting function $f_k(d,n)$.

When $k = 0$, $$ f_0(d,n) = \begin{cases} n & d = 0, \\ f_0(d-1,f_0(d-1,n)) & d > 0. \end{cases} $$ You can prove by induction that the solution is $f_0(d,n) = n$.

When $k=1$, $$ f_1(d,n) = \begin{cases} n & d = 0, \\ f_1(d-1,f_0(d-1,n)) + f_0(d-1,f_1(d-1,n)) & d > 0, \end{cases} $$ which reduces to $$ f_1(d,n) = \begin{cases} n & d = 0, \\ 2f_1(d-1,n) & d > 0. \end{cases} $$ The solution is $$ f_1(d,n) = 2^d n. $$ When $k = 2$, using the preceding formulas we get $$ f_2(d,n) = \begin{cases} n & d=0, \\ 2f_2(d-1,n) + 4^{d-1} n & d > 0. \end{cases} $$ Unrolling the recursion gives $$ \begin{align*} f_2(d,n) &= 4^{d-1} n + 2\cdot 4^{d-2} n + 2^2 \cdot 4^{d-3} n + \cdots + 2^{d-1} n + 2^d n \\ &= (2^{2d-2} + 2^{2d-3} + \cdots + 2^{d-1}+2^d) n \\ &= (2^d+1)2^{d-1} n. \end{align*} $$ Let us approximate this by $2^{2d-1}n$.

When $k = 3$, the preceding formulas show that $$ f_3(d,n) \approx \begin{cases} n & d = 0, \\ 2f_3(d-1,n) + 2^{3d} n & d > 0. \end{cases} $$ Unrolling the recursion gives $$ f_3(d,n) \approx (2^{3d} + 2^{3(d-1)+1} + 2^{3(d-2)+2} + \cdots + 2^{3(1)+d-1} + 2^d)n \approx \frac{4}{3} 2^{3d}n. $$ Continuing in this way, we find that up to constants, if $f_k(d,n) = \Theta(2^{r_kd}n)$ then $r_{k+1} = \max_{1 \leq \ell \leq k} (r_\ell + r_{k+1-\ell})$ (except for the base cases $k \leq 1$). For example, we have $$ \begin{align*} &r_0 = 0 \\ &r_1 = 1 \\ &r_2 = 2 \\ &r_3 = 3 \\ &r_4 = 4 \end{align*} $$ and so on. Indeed, induction shows that $f_k(d,n) = \Theta_k(2^{kd}n)$. With more effort, we could estimate the hidden constant.