1) a)Show that the algorithm of the Russian peasant for integer multiplication takes (n^2) time in the worst case, where n is the total number of digits in the input. b)We saw that the runtime for Mergesort complies with the following recurrence: T(n)=2T (n / 2) + n, with T (1) = 1. Show with induction (at k) that value to T(n) 2(k)*T (n 2A(k)) +kn for positive integer k