educative.io

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

Courses
,
#1

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

2 Likes
#2

Hi Mohammad Farooq,

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

#3

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

#5

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

#6

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

Hope this answers your question.

1 Like
#7

Thanks @Design_Gurus

#8

This answer and explanation in the course doesn’t detail why it’s O(2^n). My guess would have been O(n^n). I can believe it is O(2^n). It’s just not shown in this answer how we can come to that conclusion. It would be helpful if you could mathematically describe how it is O(n^2). This mathematical explanation would also help to tackle future tough non-intuitive big O calculations like this one.

1 Like