Show that if d(n) is O( ∫ (n)) and e(n) is O(g(n)), then d(n) +e(n) is O( ∫ (n)+g(n)).

Transcribed Image Text:

Algorithm Ex1(A): Input: An array A storing n ≥ 1 integers. Output: The sum of the elements in A. S← A[0] for i 1 to n - 1 do s+s+A[i] return s Algorithm Ex2(A): Input: An array A storing n> 1 integers. Output: The sum of the elements at even cells in A. S← A[0] for i 2 to n-1 by increments of 2 do s+s+A[i] return s Algorithm Ex3(A): Input: An array A storing n ≥ 1 integers. Output: The sum of the prefix sums in A. -0 S← for i 0 to n-1 do s+S+A[0] for j1 to i do s+s+A[j]