Question

C. What is the running time for the following approaches to solving the max sum of a consecutive subset of the array?

Approach 1. initialize the max sum to be the first element in the array for a subset of size 1
for each consecutive subset of that size, calc the sum of the subset
if the subset is larger than the current max, update the current max
repeat for subset sizes 2 through n

Approach 2. Divide the array in half
Return the max of the three values
result of the recursive call on the left half
result of the recursive call on the right half
the sum of the max subarray that spans the two halves (take O(n))

Answer 1

1) First algorithm is considering all size subarray hence time complexity of this algorithm can be defined as T[n]=summation(I*(n-i+1)) from I=1 to n where I is subarray size solving this we get T[n] =o(n*n)

2)Second algorithm uses divide and conquer approach and using the information calculated in more depth to compute at lower depth from top of recursion tree and at each level of recursion we are computing at cost of n operations thereby time complexity can be represented as T[n]=o(nlogn)

Please upvote.