# The time complexity of the basic solution should be exponential ie O(2^n)

The time complexity of the basic solution should be exponential ie O(2^n)

2 Likes

This is Arqam from Educative.

We are looking into this matter. We’ll get back to you as soon as possible.

Thanks

Regards,

Arqam Rehan

Thanks Mohammad Farooq for pointing this out! You are right and we have corrected it.

@Design_Gurus could you please help me understand how the basic solution runs in 2^n? Shouldn’t it be max(jump length)^n?

The time complexity of the algorithm is O(2^n) ). The worst case will happen when we can jump to all the indices from any index (i.e., every element in the array is greater than or equal to the length of the array). In this case, the while loop will run till the end of the array for every index, here is a simplified version of the loop:

``````    int start = currentIndex + 1;
while(start < jumps.length  {
// jump one step and recurse for the remaining array
int minJumps = countMinJumpsRecursive(jumps, start++);
if(minJumps != Integer.MAX_VALUE)
totalJumps = Math.min(totalJumps, minJumps + 1);
}
``````

We only removed the check `start <= end` from the while loop because the loop, in the worst case, will go till the end of the array.

Now it is easy to calculate how many recursive calls we will make. Try counting them, before reading further!

Let’s say the function is called with 5 elements array, as we called the function with ‘currentIndex=0’, this means, we make a total of four recursive calls from the first call. Here is how our recursion tree will look like:

``````                                                 currentIndex=0

1                               2                     3                4

2          3         4               3          4                4

3       4      4                         4

4
``````

So in total, we made 16 calls, which 2^(n-1), which is asymptotically equivalent to O(2^n).