$(20$ points$)$ Assume that n is a power of two. The Hadamard matrix Hn is defined as follows:

H$1=$

$1$

H$2=$

$11$

$11$

Hn $=$

Hn$/2$ Hn$/2$

Hn$/2$Hn$/2$

Design an O$($n log n$)$ algorithm that calculates the vector Hnv$,$ where n is a power of $2$ and v is a

vector of length n$.$ Justify the runtime of your algorithm by providing a recurrence relation and

solving it$.($Hint: you may assume adding two vectors of order n takes O$($n$)$ time.$)$