# What complexity does this 'how many ways to climb' algorithm have?

I have a solution to the following problem:

Given a stairway of $$n$$ stairs, which you can climb from $$1$$ to $$m$$ at the time ($$1 \leq m \leq n$$), return all the ways you can climb the stairway.

E.g. for $$n = 3$$, $$m = 2$$, the possible ways to climb are $$[2,1], [1,2], [1,1,1]$$

// outputs all the ways to react total using steps from 1 to max;
// returns the count of iterations
function permut(total, max, out) {
let iter = [{ val: [], sum: 0 }];
let count = 0;

// take the next track until there are none
for (let i of iter) {
for (let s = 1; s <= max; s++) {
// append step value to the current track
// assume constant complexity
let val = [...i.val, s];
let sum = i.sum + s;

count++;

if (sum === total) {
// we've reached the top;
// do not expand current track further
out(val);
break;
}

// add an unfinished track and start over
iter.push({ val, sum });
}
}

return count;
}


Codesandbox: https://codesandbox.io/s/busy-cdn-7idu9

However, I can't figure out the time complexity relatively to $$m$$ and $$n$$. For $$m = 1$$ the number of iterations is $$n$$, for $$m = n$$ it's $$2^n - 1$$.

Also, is there a canonical solution to this problem?

• So what if sum > total? Aug 21 '19 at 17:05
• Shouldn't happen if valid inputs are provided Aug 21 '19 at 19:04
• Can you express your algorithm in concise language-independent pseudocode, so we don't have to understand Javascript syntax or the meaning of things like iter.push() or [...i.val, s]?
– D.W.
Aug 28 '19 at 6:43
• @D.W. I don't think I can do any better in pseudocode, but I added few more comments Aug 28 '19 at 8:09
• But what is the cost of [...i.val, s]? Linear? Constant? Depends on the compiler? Aug 28 '19 at 9:15

The solution is the recursive formula:

$$S[k] = \sum_{i=1}^mS[k-i]$$

For $$m=2$$ this is the Fibonacci sequence, and the way to program it is with dynamic programming. The complexity of the dynamic programming is $$O(m \cdot n)$$.

Consider the last step before reaching step $$k$$, the number of ways to reach $$k$$ when the last step is $$i$$, is equal to the number of steps to reach $$S[k-i]$$

• Note that if $m$ is small and $n$ is large you might want to consider rewriting this in matrix form and then use fast exponentiation, to get a runtime of $O(m^3\log(n))$, or even $O(m^{2.376}\log(n))$ if you use the Coppersmith–Winograd algorithm for the matrix multiplication steps. Aug 28 '19 at 12:15
• Thanks for the answer! This assumes 𝑆[𝑘] is only calculated once per 𝑘, correct? What complexity it would be otherwise? Aug 28 '19 at 14:04
• Yes, it assumes that the calculation is done once, otherwise, with recursion (without memory) it will be $O(m^n)$ since every step makes m recursion calls Aug 28 '19 at 14:35

What you are looking for is the so-called partition function (with some constraints on the addends). A simple upper bound is the number of solutions (and thus for the runtime since you generate all of them). For the unconstrained case this is $$e^{c\sqrt n}$$ as per Siegel with c=$$\pi\sqrt\frac{2}{3}$$.

There are several specialised formulas with tighter bounds depending on certain contraints (see https://en.wikipedia.org/wiki/Partition_(number_theory) for lots of them) but generally the dominating term will be in the order of $$n!$$.

In (de Azevedo Pribitkin, W. Ramanujan J (2009) 18: 113. https://doi.org/10.1007/s11139-007-9022-z) an upper bound of $$\frac{e^{c\sqrt n}} {n^{3/4}}$$ is given. Without further assumptions about $$m$$ that is probably the best bound we can give while keeping the formula simple.

• Thanks for the answer! So where is 𝑚 in this formula? Sep 4 '19 at 7:11
• As I said, you need further assumptions about 𝑚 to decrease the bound. If for instance $m$ would be 3 you could lower the bound to $\frac{n^2}{3!} + O(n)$. (This is from the Asymptotics part of the wiki page.) The exponent $2$ coming from $m-1$. Sep 4 '19 at 10:09

I believe the question is about time complexity without DP. I read somewhere that it was mentioned the complexity is $$\mathcal O(m^n)$$ but there is a much tighter bound that I will derive below.

Based on the recursion relation we get

$$T(n) = \sum_{i=1}^m T(n-i) + m$$

where I have included the time for adding the results of the recursive calls.

Now it seems intuitive that the time complexity is exponential so lets take as an ansatz $$T(n) \sim x^n$$ and then we get

$$x^n = x^{n}(x^{-1} + x^{-2} + ... +x^{-m}) + m$$

At this point we can drop the term linear in m assuming that we will get $$x>1$$. If we do not get the same our assumption will be unjustified but we will see below that this is indeed what we get.

On summing the series on the RHS we get

$$1= \frac{1-x^{-m-1}}{1-x^{-1}}-1$$

which can be further simplified to give

$$\frac{x^m(x-2)+1}{x-1}=0$$

This solution asymptotes to 2 from below. Thus the tighter bound is $$\mathcal O(2^m)$$.