You need to answer a total of four questions, each question carries 10 points. 1. (a) Prove that the initial heaping takes O( n) operations. (b) Define Average Case Complexity. Derive an expression for the average case complexity of Binary Search. 2. Solve the following recurrences using substitution method: (a) T(n)=3T(n/2)+n,T(1)=1,n=2k (b) T(n)=2T(n/2)+n,T(1)=1,n=2k 3. Compute the optimal cost and optimal parenthesis for multiplying the matrices: A1155,,A2510,A31020,A42025 4. What is an inversion in a permutation? What is the relationship between the running time of bubble sort and number of inversions in the input array ? Find the number of inversions in [1523344152]