Computational Complexity & Fourier Transforms - Vocabulary Flashcards

Complexity depends on both the algorithm and the data structures used.
Temporal: number of basic operations for input size N. Denoted as the growth of time $T(N)$ .
Spatial: memory used beyond the input size N.(not looked at much in class)
Decision problems: yes/no questions; provide a standard way to analyze and compare problems.
Connection to P vs NP: decision form lets us ask if a problem can be solved efficiently (in polynomial time) or verified efficiently.

Decision problem: answer is either Yes or No.
Why we care: standardizes analysis and comparisons; enables reductions.
P vs NP in brief:
- If a problem can be solved in polynomial time, it’s in P.
- If a solution can be verified in polynomial time, it’s in NP.
- Decision problems are central to studying these questions and proving relationships via reductions.

Reduction: transform one problem into another so that a solution to the second solves the first.
If A reduces to B and B can be solved, then A can be solved by transforming A to B and solving B.
Analogy: solving B is no harder than solving A if you can reduce B to A efficiently.
Why reductions matter: they standardize optimization/search problems into decision problems for complexity analysis.

Optimization asks for the best solution.
Decision asks if a solution meeting a condition exists.
Often, solving the decision version helps solve the original optimization problem.
Example:
- Optimization: Find the shortest path from A to B.
- Reduce to Decision: Is there a path from A to B of length ≤ k?
- Solve the decision problem to inform the original optimization problem.

Shortest path between two cities → Decision: Is there a path of length ≤ k?
Largest set of non-overlapping tasks → Decision: Is there a non-overlapping task set of size ≥ k?
Maximum number of customers served → Decision: Can I serve at least k customers?
Graph coloring → Decision: Can the graph be colored with k colors?
Scheduling to minimize lateness → Decision: Is there a schedule with total lateness ≤ k?
Knapsack to maximize value under weight limit → Decision: Can I pack items with value ≥ k without exceeding weight W?

Step 1: Identify the goal (maximize value, minimize time, satisfy constraints).
Step 2: Add a threshold (e.g., value ≥ k, time ≤ t, solution exists).
Step 3: Rephrase as a yes/no question: Does there exist a solution that meets this threshold?

Every computational problem can be rephrased as a decision problem.
This enables the use of P, NP, and reductions to compare problems.
Central to P vs NP: if verifying a solution is easy, does that imply solving it is easy too?

P (Polynomial Time): Problems solvable by a deterministic (referring to the same input will always equal the same output) algorithm in polynomial time.
- Can Solve? Yes; Can Verify? Yes (in the usual framing for decision problems).
NP (Nondeterministic Polynomial Time): Problems where a proposed solution can be verified in polynomial time.
NP-Hard: Problems at least as hard as the hardest problems in NP; not required to be in NP.
- don’t have to be decision problems
- hard refers to the number of calculation required to solve the problem
NP-Complete: Problems that are both in NP and NP-Hard.
- hardest of the easy-to-check
Unsolvable: No algorithm can give a correct answer for all inputs (e.g., Halting Problem).

Let $T(N)$ denote an algorithm’s running time as a function of input size $N$ .
Best case: fewest operations; occurs under the most favorable inputs.
Average case: expected number of operations over all inputs of size $N$ .
Worst case: maximum operations; provides a safe upper bound.
Example (linear search):
- Best: target is the first element.
- Average: checks about half the elements.
- Worst: target not present.

Fourier transforms convert signals from time domain to frequency domain.
Foundational in:
- Audio processing
- Image compression (e.g., JPEG)
- Medical imaging (MRI, CT)
- Digital communications

DFT (Discrete Fourier Transform): rooted in Fourier’s work; analyzes finite sequences; typically O $\left(n^2\right)$ .
FFT (Fast Fourier Transform): popularized by Cooley and Tukey in 1965; dramatically reduces cost to O(n log n).
Real-life origin: Tukey’s doodle factoring input size as A×B and recursively breaking the transform; led to Cooley–Tukey algorithm.
Why it matters: demonstrates how insight-driven design can outperform brute force and enables real-time DSP.

DFT (naive) vs FFT (radix-2 recursive):
- Generality: DFT works for all sizes; FFT requires structure (e.g., power of 2 for radix-2).
- Speed: $O(n^2)$ vs $O(n \,\log\, n)$ .
- Implementation: DFT is straightforward; FFT requires recursion/bit manipulation.
- Real-world use: DFT for small datasets; FFT for large-scale processing.

DFT (Naive) – formula: $X[k] = \sum_{j=0}^{n-1} x[j] \; e^{-2\pi i j k / n}$
- Time: $O(n^2)$ due to two nested loops.
FFT (Radix-2 Recursive) – outline:
- Precondition: $n$ is a power of 2.
- If $n == 1$ return the single element.
- Split input into even-indexed and odd-indexed arrays.
- Recursively compute FFT on both halves.
- Combine results using twiddle factors.
- Time: $O(n \log n)$ due to divide-and-conquer with linear combine.

DFT:
- Per output: sum over all inputs ⇒ $T(n) = O(n^2)$ .
FFT:
- Recurrence: $T(n) = 2T(n/2) + O(n)$
- Master theorem: with $a=2, b=2, f(n)=n$ , $\log<em>b a = \log</em>2 2 = 1$ , $f(n) = \Theta(n)$ ⇒ Case 2: $T(n) = \Theta(n \log n)$ .

FFT enabled real-time digital signal processing and was critical for video encoding, audio compression, and spectral analysis.
It illustrates the power of algorithmic efficiency: the same result with far less computation.
Summary: DFT is conceptually simple but costly; FFT achieves the same results much faster, enabling big real-world impact.