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:
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:
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?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).