educative.io

What's the correct time complexity for minimum jumps to reach the end of an array?

Courses
, ,
#1

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?

#2

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.

#3

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)