Time complexity of recursive solution to minimizing the number of jumps

user_12208242 0
Viewed 139

On Geeks for Geeks the following problem is analysed:

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, they cannot move through that element. If the end isn’t reachable, return -1.

The recursive solution to this problem is to recurse on every possible step from the current element and return the minimum jumps. So if the size of the array is N, then for the first element, we have N-1 steps (choices) to recurse on (which includes recursing on the second element) and then for the second element, we have N-2 steps to recurse on (which includes recursing on the third element)... and so on. So intuitively the time complexity should be (N-1)(N-2)(N-3)....1 which is N-1! or O(N!) in big-O notation.

But the time complexity at GFG is given as:

Time complexity: O(n^n).
There are maximum n possible ways to move from a element. So maximum number of steps can be N^N so the upperbound of time complexity is O(n^n)

I know that there is a high probability of me being wrong but where could I be wrong?

recursion arrays algorithm
1 Answers

On GFG they write:

...so the upperbound of time complexity is O(^)

Your reasoning is also correct, and so O(!) is also an upper bound of the time complexity, ... a better one.

The upper bound can still be improved. Of all the possibilities at the first step, what follows does not have the same number of possibilities. True, when we make a step of 1, there is one fewer element left for what follows, but when we take a step of 2 (which is one of the -1 possibilities), there are even fewer elements left. So the product (-1)(-2)... is also an upper bound.

Actually the number of ways to find a "path" through the array corresponds to the number of compositions of , which is 2-1. As through naive recursion we will get from one composition to the next in constant time on average, the time complexity would be tightened to O(2).

I suppose that on GFG they didn't want to get into these details, and wanted to keep it straightforward, and went for an upper bound leaving lots of margin for making it more tight.

user_54598390
Related