Mathematics

Mathematics Total Marks = 40 1. Find the recurrence equation of the following algorithm and then solve the recurrence to find its time complexity as a closed form solution. Use iteration method to solve the recurrence. (10 marks) Algorithm: Test(A[1..n], B[1..n], C[1..n]) { if n= 0 then return; For i := 1 to n do C[1] := A[1] * B[i]; Test(A[2..n], B[2..n], C[2..n]); } 2. Prove the following using mathematical induction:?????(15 marks) 1. (ab)n = an bn?for every natural number n 2. 13 +23+33+…+n3 = (1+2+3+…+n)2 3. 1+3+5+7+…+(2n-1) = n2 3. Prove or disprove the following:???????(15 marks) ?1. lgvn ? O(lg n)?(vn means square root of n) ?2. lg n ? O(lgvn) ?3. 2n+1 ? O(2n)