1
$\begingroup$

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) {
  // store unfinished tracks; start with an initial track
  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?

$\endgroup$
6
  • $\begingroup$ So what if sum > total? $\endgroup$
    – gnasher729
    Aug 21 '19 at 17:05
  • 1
    $\begingroup$ Shouldn't happen if valid inputs are provided $\endgroup$
    – Pavlo
    Aug 21 '19 at 19:04
  • 1
    $\begingroup$ 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]? $\endgroup$
    – D.W.
    Aug 28 '19 at 6:43
  • $\begingroup$ @D.W. I don't think I can do any better in pseudocode, but I added few more comments $\endgroup$
    – Pavlo
    Aug 28 '19 at 8:09
  • $\begingroup$ But what is the cost of [...i.val, s]? Linear? Constant? Depends on the compiler? $\endgroup$ Aug 28 '19 at 9:15
4
$\begingroup$

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]$

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Aug 28 '19 at 12:15
  • $\begingroup$ Thanks for the answer! This assumes 𝑆[𝑘] is only calculated once per 𝑘, correct? What complexity it would be otherwise? $\endgroup$
    – Pavlo
    Aug 28 '19 at 14:04
  • 1
    $\begingroup$ 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 $\endgroup$ Aug 28 '19 at 14:35
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer! So where is 𝑚 in this formula? $\endgroup$
    – Pavlo
    Sep 4 '19 at 7:11
  • $\begingroup$ 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$. $\endgroup$
    – Eisenknurr
    Sep 4 '19 at 10:09
2
$\begingroup$

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

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