CODEWITHSUNDEEP
algorithmrecursiondata-structures
Utkarsh
Utkarsh

Reputation: 17

Time Complexity of a recursive function calling itself thrice

I'm working on my DSA. I came across a question for which the recursive func looks something like this:

private int func(int currentIndex, int[] arr, int[] memo){
        if(currentIndex >= arr.length)
            return 0;
        
        if(memo[currentIndex] > -1)
            return memo[currentIndex];
        
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i=currentIndex;i<currentIndex+3 && i<arr.length;i++){
            sum += arr[i];
            max = Math.max(max, sum - func(i+1, arr, memo));
        }
        
        memo[currentIndex] = max;
        
        return memo[currentIndex];
    }

If I'm not using memoization, by intuition at every step I've 3 choices so the complexity should be 3^n. But how do I prove it mathematically?

So far I could come up with this: T(n) = T(n-1) + T(n-2) + T(n-3) + c

Also, what should be the complexity if I use memoization? I'm completely blank here.

Upvotes: 0

Views: 162

Answers (1)

trincot
trincot

Reputation: 350345

The recurrence relation without memoization is:

      𝑇(𝑛) = 𝑇(𝑛-1) + 𝑇(𝑛-2) + 𝑇(𝑛-3) + 𝑐

This is similar to the Tribonnaci sequence, which corresponds to a complexity of about O(1.84𝑛).

With memoization it becomes a lot easier, as then the function runs in constant time when it is called with an argument that already has the result memoized. In practice this means that when one particular execution of the for loop has executed the first recursive call, the two remaining recursive calls will run in constant time, and so the recurrence relation simplifies to:

      𝑇(𝑛) = 𝑇(𝑛-1) + 𝑐

...which is O(𝑛).

Upvotes: 2

Related Questions