Sign inSign in

Fast Fourier transform

An O(nlog⁡n)O(n \log n) algorithm used to compute the discrete Fourier transform and its inverse.
as Erik Demaine defines itMITThe wording closest to all 10 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Opens up

Concepts that name this one as a prerequisite.

Lecturers

6

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    An efficient algorithm to compute the Discrete Fourier Transform in O(Nlog⁡N)O(N \log N) arithmetic operations.
    • 14:52Complexity of Basic Arithmetic
    • 12:55Fast Fourier Transform (FFT) and Integer Multiplication
    • 29:4510^500 Parallel Universes
    • 1:05:01Rotate, Compute, Rotate
  • Gilbert Strang

    MIT · Undergraduate

    An algorithm that computes the discrete Fourier transform and its inverse very quickly, enabling fast change of basis.
    • 33:40Complex Matrices and the Fast Fourier Transform
    • 29:23Change of Basis; Image Compression
  • Erik Demaine & Srini Devadas

    MIT · Undergraduate

    A divide and conquer algorithm that computes the discrete Fourier transform of a vector in O(nlog⁡n)O(n \log n) time.
  • Emily Belli

    General Atomics · Graduate

    An algorithm that computes the discrete Fourier transform and its inverse with order n log n operations.
    • 25:04Dwarfs of Computation in HPC Fusion Codes
  • Tristan Buckmaster

    Princeton University · Research

    An efficient algorithm to compute the discrete Fourier transform of a sequence.
    • 44:31Computer-Assisted Proofs in Fluid PDEs using Interval Arithmetic

Lectures that assume it

1

Connections

21

The lectures that define it or assume it, and the concepts next to it.

Concepts10

Show 4 more

Lectures11

Show 5 more

6 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.