c++ - Is a recursive function in a ternary operator evaluated twice?

Question

I came across an article that has the following statement:

maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i]; 

My question is, would maxSubArray(A, i - 1) be evaluated (called) twice (if its value is greater than 0)? Does it increase the time complexity of the code? I think so, since we would end up calling the recursive function twice (if its value is greater than 0).

Edit: Here's the code:

public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }
        
        return max;
}

and here is the related link. The above code is not directly related, since the one in my original question is from top-down DP approach, while the one added later on is from a bottom-up DP approach.

question from:https://stackoverflow.com/questions/65847532/is-a-recursive-function-in-a-ternary-operator-evaluated-twice

Answer 1

This:

maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];

is just a pseudo code notation of the relation between maxSubArray(A, i - 1) and maxSubArray(A, i). It just tells us how to compute the result for i when we do know the result for i-1. Read it like maths notation. Similar as

y = 5 * x

describes

int foo(int x) { return x*5; }

In the actual implementation the above recurrence relation is realized via:

dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);

Here dp[i - 1] is merely accessing an element of an array. Accessing the same array element twice has no impact on complexity. Given that dp[i-1] is not modified in that line, a compiler might optimize it to access dp[i-1] only once.

---

In the presence of recursion, unnecessarily calling a function twice can have an impact on complexity. Consider this example (stolen from Jarod42):

int f(int n) { 
    if (n == 0) return 1; 
    return 2 * f(n - 1); 
} 

int f(int n) { 
    if (n == 0) return 1; 
    return f(n - 1) + f(n - 1);
}

Both yield the same result, but the first has linear complexity while the second is exponential.