Shouldn’t the time complexity for minimum jump to reach the end be O(n^n) rather than O(2^n) since for every n we find n-1 to 0 and recursively down?

Hello, @Mark_Stevens,

You are right. The complexity should have been O(n^n) rather than O(2^n) since there is a maximum of `n`

possible ways to move from an element, and there are a total of `n`

possible elements, and hence the complexity goes to O(n^n). Hope this answers your query. Feel free to ask any questions if you still have any confusion.

The time complexity of the function is 2^n.

It requires some complex analysis to find the correct complexity. Let us try to explain it with a simplified version of the same problem.

The following function gets called with an array and an index. As the function makes arr[index] recursive calls to itself, can we say that its time complexity is O(max(arr)^n) (‘n’ being the number of elements in arr)? Is it possible to find a tighter limit?

```
public int calculate(int[] arr, int index) {
int max = 0, sum = 0;
for (int i = index; i < arr.length && i < index + arr[index]; i++) {
sum += arr[i];
max = Math.max(max, calculate(arr, i + 1));
}
return Math.max(max, sum);
}
```

It looks like, the time complexity is definitely not 2^n, right?

Let’s first remove the `i < index + arr[index]`

part from the loop condition, which would only (sometimes) reduce the number of iterations. By removing it, we can get a worst-case.

As in each loop iteration the function is called, counting the number of times the function is executed (at any recursion depth), is a good measure for the time complexity. Let’s call this count c.

Now define k as the number of iterations of the loop without taking recursion into account, so k is `arr.length - i`

c depends on k, so let’s speak of ck

For k = 0 there is no iteration, so just the single call, so c0 = 1. We can continue for increasing k:

```
c1 = 1 + c0 = 2
c2 = 1 + c0 + c1 = 2c1 = 4
c3 = 1 + c0 + c1 + c2 = 2c2 = 8
...
ck = 1 + ci (where i ranges from 0 to k-1) = 1 + c(k-1) + ci (where i ranges from 0 to k-2) = 2.c(k-1) = 2^k
```

When you call the function with `i=0`

, and define n as arr.length then the conclusion is that the function has a time complexity of O(2^n)