Question

1.) the following code fragments give running time analysis (Big Oh). Explain your answer:

sum2 = 0;

sum5 = 0;

for(i=1; i<=n/2; i++)

{

sum2 = sum + 2;

}

for(j=1; j<=n*n; j++)

{

sum5 = sum + 5;

}

i think it is O(n^2) since big oh finds the order of worst case which is the the second loop being n^2 complexity. but im not sure.

2.) Give an efficient algorithm along with running time analysis to find the minimum subsequence sum (Assume the minimum sum is either 0 or a negative value)

Answer 1

1.

The outer loop for(i=1; i<=n/2; i++) runs n/2 times.

Hence, the number of times the statement sum2 = sum + 52; is executed is:

= n times

The inner loop for(j=1; j<=n*n; j++) runs n² times.

Hence, the number of times the statement sum5 = sum + 5; is executed is:

= n² times

Hence, the time complexity is:

T(n) = n² + n/2 + c where c is a positive constant = O(n²)

2.

Pseudocode:

smallestSubsequenceSum(arr, n)
    Initialize min_ending_here = INT_MAX
    Initialize min_so_far = INT_MAX
    
    for i = 0 to n-1
        if min_ending_here > 0
            min_ending_here = arr[i]        
        else
            min_ending_here += arr[i]
        min_so_far = min(min_so_far, min_ending_here)

    return min_so_far

Time Complexity: O(n)