up vote 2 down vote favorite
2

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

share|improve this question
    
Please format your code for readability – Erik Nov 9 '16 at 1:05
    
Is it okay now? – John T Nov 9 '16 at 1:13
1  
@JohnT, your analysis is absolutely correct. See my answer below !!! – Shasha99 Nov 10 '16 at 6:34
up vote 1 down vote accepted

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

share|improve this answer
up vote 0 down vote

Regarding your algorithm: Although you store results in your map, your algorithms does 3 recursive call each time and only afterwards inserts the solution into the map. This means you don't reuse intermediate results.

In Order to reuse you would need to start with n=1 and then iterate until you reach your desired number of steps. This way you can be sure to reuse the result for all smaller steps:

for (int i = 1; i <= n; i++) {
  int current = map[i-1]; // you can make 1 step
  if (i > 1) 
    current += map[i-2]; // you can make 2 steps
  if (i > 2)
    current += map[i-3]; // you can make 3 steps
  map[i] = current;
}
return map[n];

Now for the complexity:

We use one map that at the end has exactly n entries. Therefore the space complexity is O(n).

We iterate once from 1 to n to make the calculation. Therefore the time complexity is also O(n).

share|improve this answer
    
You should check out my answer !!! – Shasha99 Nov 10 '16 at 12:27
    
I did. Very good example and explanation. Nevertheless the shown recursion is not dynamic programming where you reuse former results. – Erik Nov 10 '16 at 13:41
    
But the sub-problems are being re-used and each unique sub-problem is being solved only once. for example if you see recursion 1.1.1.2. it checks whether this sub-problem has already been solved or not and return the stored answer as this problem has already been solved. Thats what happens in Dynamic programming. – Shasha99 Nov 10 '16 at 13:47
    
Oh, you are right. I have missed that. Still quite confusing code :D – Erik Nov 10 '16 at 13:50
    
Hmm, Writing a recursive code for this problem is an overhead. – Shasha99 Nov 10 '16 at 13:52
up vote 0 down vote

A simple solution using memoization (O(N) time complexity and space complexity):

public static int countWaysDP(int n, int[] map) {
    map[1] = 1; // when n = 1, answer is 1
    map[2] = 2; // when n = 2, answer is 2, (1+1) and (2)
    map[3] = 4; // (1+1+1), (1+2), (2+1), (3)

    for(int i = 4;i <= n; i++)
    {
        map[i] = map[i-1] + map[i-2] + map[i-3]; 
    }

    return map[n];
}

Hope this helps!!!

share|improve this answer
1  
Are you sure my code is exponential? I tested it (see here: pastebin.com/E1tG4ST7) and it appear to run in linear time. I do prefer your solution, but don't you use tabulation, not memoization? – John T Nov 9 '16 at 23:11
    
My bad!!! Thanks for correcting me!!! – User_Targaryen Nov 10 '16 at 11:36
    
@User_Targaryen, See my answer below for better explanation !!! – Shasha99 Nov 10 '16 at 13:53
    
@User_Targaryen, Why is map[3] = 4 and not = 3? – John T Dec 5 '16 at 11:19
1  
@JohnT: I have commented the reason behind map[3]=4.. (all 1 steps) or (1 step then 2 step) or (2 step then 1 step) or (3 steps directly) – User_Targaryen Dec 5 '16 at 15:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.