Q:

Time and space complexity of dynamic programming algorithm

This algorithm is from Cracking the Coding Interview, 5th Edition, found here: https://www.geekbooks.me/book/view/cracking-the-coding-interview-5th-edition 
A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or
3 steps at a time. Implement a method to count how many possible ways the child
can run up the stairs.
Algorithm:
 public static int countWaysDP(int n, int[] map) {
    if (n < 0) {
        return 0;
    } else if (n == 0) {
        return 1;
    } else if (map[n] > -1) {
        return map[n];
    } else {
        map[n] = countWaysDP(n - 1, map) + 
                 countWaysDP(n - 2, map) + 
                 countWaysDP(n - 3, map);
        return map[n];
        }
}

What is the time and space complexity of this algorithm?  I think since memoization is used, the results are stored so values don't get calculated multiple times like in the pure recursive method.  Since there are three calls to countWaysDP the time complexity is O(3n) which is an element of O(n).  The space complexity would be O(n+n) one n for the size of map and one n for the recursive call stack, which is also an element of O(n).  Is my reasoning correct?
Thanks

A:

Let us execute the code:
Note the notation of recursion stack. 1.2.3. means third recursion countWaysDP(n-5) of second recursion countWaysDP(n-2) of countWaysDP(n).
Consider n=6

1. countWaysDP(6)
1.1. countWaysDP(5)
1.1.1. countWaysDP(4)
1.1.1.1. countWaysDP(3)
1.1.1.1.1. countWaysDP(2)
1.1.1.1.1.1. countWaysDP(1)

1.1.1.1.1.1.1. countWaysDP(0) //returns 1
1.1.1.1.1.1.2. countWaysDP(-1) //returns 0
1.1.1.1.1.1.3. countWaysDP(-2) //returns 0                        -> map[1] = 1 <-

1.1.1.1.1.2. countWaysDP(0) //return 1
1.1.1.1.1.3. countWaysDP(-1) //return 0                           -> map[2] = 2 <-

1.1.1.1.2. countWaysDP(1) //already claculated, returns map[1]
1.1.1.1.3. countWaysDP(0) //returns 1                             ->map[3] = 4 <-

1.1.1.2. countWaysDP(2) //already present, returns map[2]
1.1.1.3. countWaysDP(1) //already present, returns map[1]         -> map[4] = 7 <-

1.1.2. countWaysDP(3) //already present, returns map[3]
1.1.3. countWaysDP(2) //already present, returns map[2]           -> map[5] = 13 <-

1.2. countWaysDP(4) //already present, returns map[4]
1.3. countWaysDP(3) //already present, returns map[3]             -> map[6] = 24 <-

Now assume that involking a method is O(1) operation. The total time taken for this example would be:
6 + 3 + (2 + 2 + 2 + 2 + 2) = 19

So yes, you are correct about the TIME. Its 3n as the leftmost recursion path is taking O(n) and then all other calls are O(2n). 
The recursion stack would take O(n) as the maximum stack depth is n + 3 and your map will take O(n) space. So yes again, the SPACE is O(n + n) = O(n).

