CODEWITHSUNDEEP
javaarraysalgorithmtime-complexity
aatwork
aatwork

Reputation: 2270

Minimum Jump Array Recursive Time Complexity should be O(n^n) or O(n!)

I was checking "minimum number of jumps to reach the end" problem in GeekforGeeks https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/ . I got confused about the time complexity mentioned there which is O(n^n).

// Returns minimum number of
// jumps to reach arr[h] from arr[l]
static int minJumps(int arr[], int l, int h)
{
    // Base case: when source
    // and destination are same
    if (h == l)
        return 0;
 
    // When nothing is reachable
    // from the given source
    if (arr[l] == 0)
        return Integer.MAX_VALUE;
 
    // Traverse through all the points
    // reachable from arr[l]. Recursively
    // get the minimum number of jumps
    // needed to reach arr[h] from these
    // reachable points.
    int min = Integer.MAX_VALUE;
    for (int i = l + 1; i <= h
                        && i <= l + arr[l];
         i++) {
        int jumps = minJumps(arr, i, h);
        if (jumps != Integer.MAX_VALUE && jumps + 1 < min)
            min = jumps + 1;
    }
    return min;
}

If I see the above code block, minJumps(arr, i, h) recursive call is getting called from i=l+1. So in every recursive step, l(start position) is getting incremented by 1. Time complexity should be calculated as below.

T(N) = (n-1)*(n-2)*(n-3)...*1
     = (n-1)!

I am not getting why time complexity is O(n^n). In few other places also, I saw time complexity for this recursive solution is mentioned as O(n^n) without a proper explanation. Please help me out with a simple explanation & point out what I am missing here.

Upvotes: 3

Views: 271

Answers (1)

potter1024
potter1024

Reputation: 205

I can see the recurse relation as T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) + ... + T(0), since the loop is from l to h (ignore the if condition for now). So for an interval [l,h] every value in that interval will be called in the worst case that is minJumps(l+1, h), minJumps(l+2, h) ... minJumps(h, h) and it can be noticed that the above recurse relation holds here.

Now, solving the relation, we can write it as T(n) = T(n-1) + T(n-1) as T(n-1) = T(n-2) + T(n-3) + T(n-4) + ... + T(0). Hence T(n) = 2 * T(n-1) which boils down to O(2^n).

The time complexity of the mentioned algorithm should be O(2^n).

Upvotes: 2

Related Questions