- (i). [7 marks] Given g(1) = 1, show the solution of g(n) = g(n -...

Transcribed Image Text:

- (i). [7 marks] Given g(1) = 1, show the solution of g(n) = g(n - 1) + 4n is O(n). - (ii). [7 marks] Analyze the time complexity of MAXSUBARRAYSUM algorithm. Algorithm MAXSUBARRAYSUM (A, l, h) 1: if=h 2: 23 3: 4: 5: 6: 7: 8: 9: return A[I] mid = [(1+h)/2] left-cross-sum = -00 sum = 0 for imid downto l sum = sum + A[i] if sum left-cross-sum left-cross-sum = sum 10: right-cross-sum = - for j = mid + 1 to h 11: sum = 0 12: 13: sum = sum + A[j] 14: if sum 15: 16: right-cross-sum right-cross-sum = sum cross-sum = left-cross-sum + right-cross-sum 17: left-sum = maxSubArraySum(A, l, mid) 18: 19: right-sum = maxSubArraySum(A, mid + 1, h) return max(left-sum, right-sum, cross-sum) - (i). [7 marks] Given g(1) = 1, show the solution of g(n) = g(n - 1) + 4n is O(n). - (ii). [7 marks] Analyze the time complexity of MAXSUBARRAYSUM algorithm. Algorithm MAXSUBARRAYSUM (A, l, h) 1: if=h 2: 23 3: 4: 5: 6: 7: 8: 9: return A[I] mid = [(1+h)/2] left-cross-sum = -00 sum = 0 for imid downto l sum = sum + A[i] if sum left-cross-sum left-cross-sum = sum 10: right-cross-sum = - for j = mid + 1 to h 11: sum = 0 12: 13: sum = sum + A[j] 14: if sum 15: 16: right-cross-sum right-cross-sum = sum cross-sum = left-cross-sum + right-cross-sum 17: left-sum = maxSubArraySum(A, l, mid) 18: 19: right-sum = maxSubArraySum(A, mid + 1, h) return max(left-sum, right-sum, cross-sum)