Number of ways to get from top left corner to bottom right corner in MxN grid while moving only down or right. What is time and space complexity?

user_9064356 0
Viewed 99

The problem: find a number of possible ways from top left corner to bottom right corner in MxN grid while you can only move down or right.

Here are two algorithms I have written. Results look ok but I can't figure out time and space complexity, I have some guesses about what the complexities might be but I can't prove them in a "proper" way.

Naive algorithm:

    function gridTravel(m, n) {
      if(m<1 || n<1) return 0;
      if (m === 1 || n === 1) return 1;
      return gridTravel(m-1, n) + gridTravel(m, n-1);
    };
    console.log(gridTravel(10,10));

My guesses:

  • Space complexity - O(n+m)? The longest possible call stack seems to scale "linearly" so assuming some approximation it would be O(n+m) but I can't really prove it or disprove it.
  • Time complexity is exponential because each position can create 2 new positions - O(2^n) or O(2^n+m), not sure which is more fitting.
                   m:n
        m-1:n                m:n-1
    m-2:n  m-1:n-1     m-1:n-1   m:n-2

But again, I don't feel confident with this explanation because it isn't simmetrical tree it just looks like it at the beginning.

Naive algo + memoization:


    seenGrids = {};
    const gridTravel = (m, n) => {
      if(m<1 || n<1) return 0;
      if (m === 1 || n === 1) return 1;
      if (`${m}:${n}` in seenGrids || `${n}:${m}` in seenGrids) {
        return seenGrids[`${m}:${n}`] || seenGrids[`${n}:${m}`];
      }
      seenGrids[`${m}:${n}`] = gridTravel(m-1, n) + gridTravel(m, n-1);
      return seenGrids[`${m}:${n}`];
    };

My guesses:

  • Space - O(n*m)? Call stack still seems to be linear but now we have this growing object seenGrids which based on my intuition should scale kind of in a quadratic way? I have no idea how to prove it or disprove it, when I ran console.log(Object.keys(seenGrids).length) for 200x200 grid I got 19900 which isn't either m*n or m+n so is it linear or quadratic?
  • Time - O(n*m)? - this is the hardest for me to wrap my head around. It shouldn't be exponential anymore because a lot of subtrees are skipped thanks to saved answers but I have no idea how to derive time complexity in a "proper" way.
space-complexity big-o time-complexity algorithm javascript
1 Answers

First Algorithm:

For the time complexity, the easiest prove is your method! I mean the computation tree of the recursive function. As you can see, there is a binary tree for the expansion, and the maximum length of the tree is min(n,m). Hence, the time complexity is in O(2^(min(m,n))).

For the space complexity, as you have noted, the computation of the stack will be done in a depth-first manner. Hence, as the maximum branch of each node is 2 and the maximum length of the tree is min(m,n) (as discussed in the previous paragraph), the space complexity will be 2 min(m,n).

Second Algorithm:

As the maximum different combination of inputs is m * n ([1, 2, ..., m] and [1, 2, ..., n] for the first and the second inputs of the function, respectively), and the worst case of the stack call is in O(min(m, n)), the space complexity is in O(m * n), which is the size of the memory array.

For the time complexity, we can ensure that each element of the array will be computed once (as it's memorized). Hence, independent of the complexity of recursive callbacks, and due to depth-first computing of the recursion (from bottom-up), the time complexity of the second algorithm is in O(m * n).

user_37688710
Related