# Advanced Algorithm Design & Analysis: Polynomials and the FFT

# Introduction

A naive attempt at multiplying two polynomials of the same degree

would have a runtime of

time. This is called the discrete Fourier transform (DFT). The fast Fourier transform (FFT) reduces this to