(a) what is the running time?

(b) What makes the method described above so fast is that, for a vector v of length n=2^(k) the matrix-vector product can be computed in time ... continued in picture.

Help pls

Problem 1-2. Dimensionality reduction Dimensionality reduction is a widely-used technique for accelerating computations on high-dimensional data, by replacing them with a lower-dimensional "summary" that preserves the key properties of the original data, typically the approximate distances of points. The key step in fast dimension- ality reduction is multiplying a vector by a matrix from the following family of special matrices, Ho, H Ho is the l 1 matrix [1] For k>0, H is the 2* x 2* matrix (a) If you naively multiply a length n vector with a length n n matrix, what is the running time? (b) What makes the method described above so fast is that, for a vector of lengthn 2% the matrix-vector product HeT can be computed in time O(n logn). Give a recursive, divide and conquer algorithm for this. Show how to do this (and as usual, prove the correctness and time bound of your algorithm) Hint: The idea is similar to matrix multiplication. In particular, given a problem of size n (where you multiply a vector of size 2k with a matrix Hk of size 2k 2k) can you find the solution two subproblems of size n/2? How much can you afford for the divide/combine steps of the divide and conquer algorithm