0

I am seeking assistance in determining the time complexity of a given source code, which appears to be of the order O(n^3). Could someone kindly assist me in evaluating its time complexity?:

public static int function(int[] arr, int index) {

        if (index <= 0) {
            return arr[0];
        }

        int one = function(arr, index - 1);
        int two = function(arr, index - 2);
        int three = function(arr, index - 4);

        if (one > two) {
            return one;
        } else if (two > three) {
            return three;
        } else {
            return one;
        }
    }

I expecting that the time complexity is o(n^3)

Chaosfire
  • 4,818
  • 4
  • 8
  • 23
computer science
  • 1
  • 2
  • It looks more like O(3^n) than O(n^3). In each recursion step, it calls itself 3 times. T(n) = 3 T(n-1), since it multiplies by 3 in each step, the order would be O(3^n). – Andrés Alcarraz May 26 '23 at 16:26

1 Answers1

0

In each recursion step, the function calls itself three times, while reducing the index by substracting constant values.

Time for index = n would be:

T(n) = 3*T(n-1) = 3*3 T(n-2) ... ≅ 3*3...*3 T(0) = 3^n * T(0)

Which is exponential with base 3: O(3^n).

Andrés Alcarraz
  • 1,570
  • 1
  • 12
  • 21