1. Give, using big oh notation, the worst case running times of the following procedures as a function of n 0.

(a). procedure unknown

for i =1 to n 1 do

for j =i + 1 to n do

for k =1 to j do

{statements requiring O(1) time}

endfor

endfor

endfor

(b). procedure quiteodd

for i =1 to n do

if odd(i) then

for j =i to n do

x x + 1

endfor

for j =1 to i do

y y + 1

endfor

endif

endfor

(c). function recursion (n)

if n <= 1 then

return (1)

else

return (recursion (n 1) + recursion (n 1))

endif

2.

The function max (i, n) given below returns the largest element in positions i through i + n 1 of an integer array A. Assume for convenience that n is a power of 2.

function max(i, n)

if n = 1 then

return (A[i])

else

m1 max (i, n/2)

m2 max (i + n/2, n/2)

if m1 < m2 then

return (m2)

else

return (m1)

endif

endif

(a). Let T(n) denote the worst-case time taken by max with the second argument n. Note that n is the number of elements of which the largest is to be determined. Write an equation expressing T(n) in terms of T(j) for j < n and constants that represent the times taken by statements of the program.

(b). Obtain a big theta bound on T(n).