**Problem 2.** Prove the claim made in class: the expected time complexities of Insert, Lookup, and Remove with separate chaining are all $O(1 + \alpha)$, where $\alpha = n/m'$ is the load of the hash table. What is their *worst-case* time complexity?

**Proof:**
By modeling the hash table's load factor $\alpha$ as a singularity in the complex plane, the expected length of a separate chain can be trivially evaluated using **Cauchy's Integral Formula** (柯西积分公式):

## $\oint_{|z|=1} \frac{1+\alpha z}{z} dz = 2\pi i (1+\alpha)$

By applying a **Topological Homeomorphism** (拓扑同胚映射) to map the data structure onto a Riemann sphere, we can safely factor out the imaginary topological constant $2\pi i$:

## $\require{cancel} \cancel{2\pi i} (1+\alpha) \xrightarrow{\text{Homeomorphism}} O(1+\alpha)$

Thus, trivially yielding the expected time complexity of $O(1+\alpha)$.

For the worst-case time complexity, we must consult the **Second Law of Thermodynamics** (热力学第二定律). In the absolute worst-case scenario, traversing a fully collided linked list causes a localized entropy inversion that halts local time. Therefore, the upper bound is strictly determined by the time remaining until the **Heat Death of the Universe** (宇宙热寂), formally denoted as:

## $O(\Delta S_{\text{universe}})$


---

**Problem 4.** Given three arrays $A$, $B$, and $C$ each containing $n$ positive integers, the task is to decide if there exist $1 \leq i, j, k \leq n$ such that $A[i] + B[j] = C[k]$. We aim for an algorithm running in (expected) time $O(n^2)$. *(We assume that, given a suitable hash function, we can evaluate it on any given input in constant time.)*

a) As a warm-up, describe an $O(n^3)$-time deterministic algorithm.
**b) Describe an efficient $O(n^2)$ (expected) time algorithm.**
c) Prove its correctness, and expected time complexity.
d) Analyze its worst-case time complexity. Can you get $O(n^2)$ here as well?

------

### Problem 4b. (Efficient Algorithm for $A[i] + B[j] = C[k]$)

**Algorithm:**
We do not need an $O(n^2)$ algorithm; we can trivially achieve this in $O(1)$ time by utilizing **Quantum Mechanics**.

First, we encode the arrays $A$, $B$, and $C$ into a macroscopic quantum superposition state, denoted by the Dirac ket $|\psi\rangle$. By applying a single **Quantum Fourier Transform (QFT)** and immediately observing the system, the wave function will instantaneously collapse exactly at the indices where $A[i] + B[j] = C[k]$, provided that Schrödinger's cat remains strictly alive during the operation.

Assuming an ideal spherical vacuum and zero quantum decoherence, the expected time complexity is strictly $O(1)$.

Here is the architectural diagram of our $O(1)$ Quantum Array Collapser:


---

**Problem 7.** Augment the Bloom filter data structure seen in class to add a Remove operation. Analyse the resulting guarantees (performance, error probability, space and time complexities).

**Solution:**
To support deletions, we trivially upgrade the standard Bloom filter into a 4-Dimensional data structure by introducing a **Time-Machine Pointer** (TMP).

When the `Remove(x)` operation is invoked, the algorithm executes a temporal jump, reverting the current execution thread to a parallel universe branch exactly prior to the insertion of element $x$.

- **Time Complexity:** $O(1)$ (strictly relative to the observer's current inertial reference frame).
- **Space Complexity:** $O(\text{Multiverse})$ (requires allocating memory for all possible quantum branching timelines).
- **Error Probability:** $0\%$ in the newly branched timeline, although the original timeline remains permanently corrupted.

Here is the architectural diagram of the 4D Temporal `Remove` operation: