HMM Forward Algorithm (Evaluation)

The evaluation problem asks for the observation probability $P(O \mid \lambda)$ given HMM parameters $\lambda = (A, B, \pi)$ and an observation sequence $O = o_1 o_2 \dots o_T$. Summing over state sequences requires $N^T$ paths, which is intractable; the forward algorithm defines forward variables $\alpha_t(j) = P(o_1 \dots o_t, q_t = j \mid \lambda)$ — the joint probability of being in state $j$ at time $t$ after emitting $o_1 \dots o_t$ — and recurses

initialized with $\alpha_1(j) = \pi_j b_j(o_1)$ and terminating at $P(O \mid \lambda) = \sum_j \alpha_T(j)$. Each step sums $N$ transitions for each of $N$ states, reducing the cost from $O(N^T)$ path enumeration to $O(N^2 T)$.

scoring sequences in speech recognition and bio-sequence analysis, and as the E-step machinery of Baum-Welch; interviews often ask for the forward-variable definition and how forward differs from Viterbi (sum vs max).

direct summation over hidden states is exponential, and the forward algorithm caches subproblems to make likelihood computation polynomial; the cost is an $O(N^2)$ transition sum per step and $O(NT)$ storage (rollable to $O(N)$).

Write the forward recursion $\alpha_t(j) = [\sum_i \alpha_{t-1}(i)a_{ij}]b_j(o_t)$ with its initialization $\alpha_1(j)$ and termination $P(O \mid \lambda)$?

Why is naive computation of $P(O \mid \lambda)$ exponential in $O(N^T)$, and how does the forward algorithm reduce it to $O(N^2T)$?

How do the forward algorithm and Viterbi differ (sum vs max, and what each outputs)?

What is the probabilistic meaning of $\alpha_t(j)$, and how does it combine with the backward variable $\beta_t(j)$ to give $P(q_t = j \mid O, \lambda)$?

Compute $P(O \mid \lambda)$ by hand for a concrete HMM (e.g. $N=2$, $T=3$), showing each forward step?