1. Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then the product d(n)e(n) is O( f (n)g(n)).

2. Give a big-Oh characterization, in terms of n, of the running time of the Ex1 function shown in Code Fragment 4.6.

Code Fragment 4.6: Some algorithms.

Algorithm Ex1(A):

Input: An array A storing n ≥ 1 integers.

Output: The sum of the elements in A.

s←A[0]

fori←1to n−1 do

s←s+A[i]

returns

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]

fori←2to n−1 by increments of 2 do

s←s+A[i]

returns

Algorithm Ex3(A):

Input: An array A storing n ≥ 1 integers.

Output: The sum of the prefix sums in A.

s←0

fori←0to n−1 do

s←s+A[0]

forj←1 to i do

s←s+A[ j]

returns

Algorithm Ex4(A):

Input: An array A storing n ≥ 1 integers.

Output: The sum of the prefix sums in A.

s←A[0]

t←s

fori←1to n−1 do

s←s+A[i]

t←t +s

returnt

Algorithm Ex5(A,B):

Input: Arrays A and B each storing n ≥ 1 integers.

Output: The number of elements in B equal to the sum of prefix sums in A.

c←0

fori←0to n−1 do

s←0

forj←0 to n−1 do

s←s+A[0]

fork←1to j do

s←s+A[k]

ifB[i] = s then

c←c+1

returnc