GATE CS 2014 Set 1 Q41 — Asymptotic Worst Case Time and Space Complexity

Let us analyze the behavior of the function MyX step-by-step:

1. Initialization and First Loop:

   int Y = 0;
   for(i = 0; i < size; i++) 
       Y = Y + E[i];

   This loop calculates the sum of all elements in the array $E$ and stores it in $Y$. Thus, initially, $Y = \sum_{p=0}^{\text{size}-1} E[p]$. Note that the entire array is itself a valid sub-array.
2. Nested Loops for Sub-arrays:

   for(i = 0; i < size; i++) 
       for(j = i; j < size; j++) { 
           Z = 0; 
           for(k = i; k <= j; k++) 
              Z = Z + E[k];
           ...
       }

   The outer loops with indices $i$ and $j$ define the boundaries of every possible contiguous sub-array $E[i \dots j]$ of $E$. The innermost loop with index $k$ computes the sum of the elements in this sub-array $E[i \dots j]$ and stores it in $Z$.
3. Updating the Maximum Sum:

   if(Z > Y) 
      Y = Z;

   If the sum of the current sub-array ($Z$) is strictly greater than the current maximum sum ($Y$), then $Y$ is updated to $Z$.

Since $Y$ is initialized to the sum of the entire array and is updated whenever a larger sub-array sum is found, the function eventually returns the maximum possible sum of elements in any sub-array of array $E$ (which is the brute-force solution to the Maximum Subarray Sum problem).