Problem 6. (20 pts) In this question, we will discuss multiplying a (nxn)-matrix M with an-dimensional vector (a) (5 pts) Describe the naive loop-based algorithm for computing Mu and argue it runs in time (n2) (b) (15 pts) The Hadamard matrix is (2 2 matrix defined for any integer k > 0 by the following recursive definition: H0 [1] which is a (1 1)-matrix, and Hk+1 for k 2 0 Hk-Hk So, for example, H1 = 1-1 and H2 = 1 1 -1 -1, and Hs is a (8 x 8)-matrix Given n which is a power of 2 (i.e., n - 2* for some k), describe an algorithm whose input is a n- dimensional vector v, and returns the product of the Hadmard matrix with the given vector, ie. Hk . U. Explain why your algorithm is correct and prove that its runtime is O(n log(n)). You may use the fact (without proving it) that adding/subtracting two n-dimensional vectors takes O(n) time