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.