4answer Q40

37. Give a O(lg n) algorithm that computes the remainder when x" is divided by p. For simplicity, you may assume that n is a power of 2. That is, n = 2k for some positive integer k. 38. Explain in English what functions are in the following sets. (a) n (1) (b) 0 (2011) () 0 (0 (204)) 39. Show that the function f(n) = | n2 = sin n| is in neither O(n) nor 2(n). 40. Justify the correctness of the following statements assuming that f(n) and g(n) are asymptotically positive functions. (a) f(n) + g(n) E O (max (f(n)), 9 (n)) (b) f(n) E 22(f(n)) (c) f(n) + o(f(n)) E O(f(n)), where o(f(n)) means any function g(n) E o(f(n)) 41. Give an algorithm for the following problem. Given a list of n distinct positive integers, partition the list into two sublists, each of size 1/2, such that the difference between the sums of the integers in the two sublists is minimized. Determine the time complexity of your algorithm. You may