$[20$pts$]$ To evaluate a polynomial of degree $n$ at $v$ and $-v,$ one could simply call HornerEval twice, involving $2n$ multiplications and $2n$ additions.

Describe and analyze an algorithm that uses HornerEval and solves this problem using only $n$ multiplications and $n+1$ additions $($or subtractions$).$

Hint: Split the coefficient array of the polynomial into even$-$ and odd$-$indexed terms.

A generalization of this process is the basis of the famous Fast Fourier Transform, which we will cover later in this course.