3
$\begingroup$

I'm having trouble determining the complexity of an algorithm. Let's say the number of operations of my algorithm is described by $$f(x, k) = f(x, k-1) + f(x-1, k-1) + f(x-2, k-1) + \dots + f(1, k-1)$$ where $f(x, 1) = x$

How can I describe the growth of $f(x)$ in terms of

  1. $x$
  2. $k$
  3. $x$ when $k=x-1$

For 1), I believe $f(x, k)$ would be exponential in $x$ as $k$ can be taken to be a constant which would reduce the above equation to being similar to

$$f(x) = f(x-1) + f(x-2) + \dots + f(1) $$

Similarly, for 2), I believe $f(x, k)$ would be exponential in $k$ as I would need to take $x$ as a constant which would lead to the below equation

$$f(k) = xf(k-1) $$

Need help with 3) and also validating my thinking for 1) and 2)

$\endgroup$
4
  • $\begingroup$ I dont see when the recursion ends. f(x,2)=f(x,1)+f(x-1,2)=x+(f(x-1,1)+f(x-2,2)) = x + (x-1) + (f(x-2,1)+f(x-3,2)) .. $\endgroup$ Sep 14, 2018 at 18:32
  • $\begingroup$ @RandomPerfectHashFunction Made a mistake with that equation I had. Please look at the updated question. $\endgroup$
    – nave
    Sep 15, 2018 at 0:23
  • $\begingroup$ The above equation can be written as $f(x, k) = f(x, k-1) + f(x-1, k)$. Does that give any clues? May be generating functions could solve this? You perhaps need a boundary condition as well ($f(0, k)$ = something) to solve this. $\endgroup$ Sep 15, 2018 at 4:12
  • $\begingroup$ I had initially written this as $f(x,k)$=$f(x,k−1)$+$f(x−1,k)$ in my question as well, but as @RandomPerfectHashFunction pointed out, this recurrence does not end as there is always a term with $f(x, k)$ .... So it seems the 2 equations are actually not equivalent given there is only a base case for $f(x,1)$ $\endgroup$
    – nave
    Sep 16, 2018 at 22:09

3 Answers 3

3
$\begingroup$

You can write your recursion as \begin{equation} \begin{split} f(x,k) &= \sum\limits_{i_1=1}^x f(i_1,k-1)\\ &= \sum\limits_{i_1=1}^x \sum\limits_{i_2=1}^{i_1} f(i_2,k-2)\\ &= \vdots \\ &= \sum\limits_{i_1=1}^x \sum\limits_{i_2=1}^{i_1} \ldots \sum\limits_{i_{k-1}=1}^{i_{k-2}} f(i_{k-1},1)\\ &= \sum\limits_{i_1=1}^x \sum\limits_{i_2=1}^{i_1} \ldots \sum\limits_{i_{k-1}=1}^{i_{k-2}} i_{k-1}\\ \end{split} \end{equation} We know that from Faulhaber's formula \begin{equation} \sum\limits_{i_{k-1}=1}^{i_{k-2}} i_{k-1} = \frac{1}{2}O(i_{k-2}^2) \end{equation} So \begin{equation} f(x,k) = \sum\limits_{i_1=1}^x \sum\limits_{i_2=1}^{i_1} \ldots \sum\limits_{i_{k-2}=1}^{i_{k-3}} \frac{1}{2}O(i_{k-2}^2) \end{equation} Also \begin{equation} \sum\limits_{i_{k-2}=1}^{i_{k-3}} O(i_{k-2}^2) = \frac{1}{3}O(i_{k-3}^3) \end{equation} If you keep doing this, you'd get \begin{equation} f(x,k) = \frac{1}{2 \times 3 \times 4 \times \ldots \times (k-1) } \sum\limits_{i_1=1}^x O(i_1^{k-1}) = \frac{1}{2 \times 3 \times 4 \times \ldots \times (k-1) \times k} O(x^k) = \frac{1}{k!} O(x^k) \end{equation}

$\endgroup$
3
$\begingroup$

The answers to all three questions become easier once we proved the following formula for all positive integer $k$ and $x$. $$ f(x,k) = \frac{x(x+1)(x+2)\cdots(x+k-1)}{k!}$$ Proof: The formula is easily seen to be true for $k=1$ and all positive integer $x$.

Assume the formula is true for some positive integer $k$ and all positive integer $x$. Then, $$\begin{align} &f(x, k+1)\\ &=f(x, k) + f(x-1, k) + f(x-2, k) + \dots + f(1, k)\\ &=\frac1{k!}(x(x+1)(x+2)\cdots(x+k-1) + (x-1)x(x+1)(x+2)\cdots(x+k-2)\\ &\quad\quad+\cdots+1\cdot2\cdots k\\ &=\frac1{k!}\left(\frac{x(x+1)(x+2)\cdots(x+k)-(x-1)x(x+1)\cdots(x+k-1)}{k+1}\right.\\ &\quad\quad+\frac{(x-1)x(x+1)\cdots(x+k-1)-(x-2)(x-1)x\cdots(x+k-2)}{k+1}\\ &\quad\quad+\cdots\\ &\quad\quad+\frac{2\cdot3\cdots(k+1)-1\cdot2\cdots k}{k+1}\\ &\quad\quad+\left.\frac{1\cdot2\cdots k}{k+1}\right)\\ &=\frac1{k!}\frac{x(x+1)(x+2)\cdots(x+k)}{k+1}\\ &=\frac{x(x+1)(x+2)\cdots(x+(k+1)-1)}{(k+1)!}\end{align}$$

By mathematical induction on $k$, the formula is true for all positive integer $k$ and $x$.


Here are the answers to your three cases.

1) For fixed $k$ and $x\to\infty$, $$f(x,k)=\frac{x^k}{k!}\frac xx\frac{x+1}x\cdots\frac{x+k-1}{x}\sim\frac{x^k}{k!}$$ That is, $f(x,k)=\Omega(x^k)$.

2) For fixed $x$ and $k\to\infty$, by Stirling's approximation, $$\begin{align}f(x,k)&=\frac{(x-1+k)!}{(x-1)!k!}\\ &\sim\frac1{(x-1)!}\frac{\sqrt{2\pi(x-1+k)}\left(\frac{x-1+k}{e}\right)^{x-1+k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}\\ &=\frac1{(x-1)!}\sqrt\frac{x-1+k}k (x-1+k)^{x-1}\left(\frac{x-1+k}{k}\right)^k\frac{1}{e^{x-1}}\\ &=\frac1{(x-1)!}\sqrt\frac{x-1+k}k\left(\frac{x-1+k}{k}\right)^{x-1}k^{x-1}\left(1+\frac{1}{\frac k{x-1}}\right)^{\frac k{x-1}(x-1)}\frac{1}{e^{x-1}}\\ &\sim\frac1{(x-1)!}k^{x-1}e^{x-1}\frac{1}{e^{x-1}}\\ &=\frac{k^{x-1}}{(x-1)!}\end{align}$$ That is, $f(x,k)=\Omega(k^{x-1})$

3) Let $k=x-1$ go to infinity, again by Stirling's approximation, $$f(x,k) = \frac{(2k)!}{k!k!}\sim \frac{\sqrt{2\pi2k}\left(\frac{2k}{e}\right)^{2k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}=\frac{2^{2k}}{\sqrt{\pi k}}$$ That is, $f(k+1,k)=\Omega(k^{-1/2}2^{2k})$.

$\endgroup$
2
  • $\begingroup$ a few questions ... 1) How did you come up with the initial formula for $f(x, k)$ which you proved? 2) For fixed $k$ part, why do we need to divide by $x$ raised to power of $k$? 3) For fixed $x$ part, could you please elaborate on going from the second term to the third term and from the third term to the fourth term? $\endgroup$
    – nave
    Sep 16, 2018 at 22:14
  • $\begingroup$ 1) By the recurrence relation we can compute to obtain $f(x,1)=x$ and $f(x,2)=n(n+1)/2$ and $f(x,3)=n(n+1)(n+2)/3 $. Then observe the pattern. 2) If $k$ is fixed, then $x\sim x, (x+1)\sim x, \cdots, (x+k-1)\sim x$ when $x\to \infty$. So you have a product of $k$ $x$'s. 3) I will update the answer. $\endgroup$
    – John L.
    Sep 16, 2018 at 22:16
1
$\begingroup$

For $k \geq 1$, define $$ T_k(z) = \sum_{n=0}^\infty f(n,k) z^n, $$ where we define $f(0,k) = 0$ (which agrees with the definition for $k=1$).

Since $f(n,1) = n$ for all $n$, we get $$ T_1(z) = \sum_{n=0}^\infty nz^n = z\sum_{n=0}^\infty nz^{n-1} = z \frac{d}{dz} \sum_{n=0}^\infty z^n = z \frac{d}{dz} \frac{1}{1-z} = \frac{z}{(1-z)^2}. $$ For $k > 1$, we have $$ T_k(z) = \sum_{n=0}^\infty f(n,k)z^n = \sum_{n=0}^\infty \sum_{m=0}^n f(m,k-1) z^n = \sum_{m=0}^\infty f(m,k-1) \sum_{n=m}^\infty z^n = \\ \sum_{m=0}^\infty f(m,k-1) z^m \sum_{n=0}^\infty z^n = \sum_{m=0}^\infty f(m,k-1) \frac{z^m}{1-z} = \frac{T_{k-1}(z)}{1-z}. $$ A short induction shows that $$ T_k(z) = \frac{z}{(1-z)^{k+1}}. $$ You can now consider the bivariate generating function $$ S(z,w) = \sum_{n=0}^\infty \sum_{k=1}^\infty f(n,k) z^n w^k = \sum_{k=1}^\infty w^k T_k(z) = z \sum_{k=1}^\infty w^k (1-z)^{-k-1} = \\ \frac{z}{1-z} \sum_{k=1}^\infty \left(\frac{w}{1-z}\right)^k = \frac{zw}{(1-z)^2}\frac{1}{1-w/(1-z)} = \frac{zw}{(1-z)(1-z-w)}. $$ From here you can in principle deduce all asymptotic properties. It is also easy to extract the exact formula, since the coefficients of $\frac{1}{(1-z)^k}$ are known.

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