#trigram-hmm

Question 1: Single choice

A trigram HMM tagger scores $P(t_i \mid t_{i-2}, t_{i-1})\,P(w_i \mid t_i)$ . A tag dictionary lists for each word the tags it can take, at most $K$ per word, out of a full tag set $T$ . How fast can the Viterbi algorithm find the best tag sequence for an $n$ -word sentence?

$O(nK^3)$ 1
$O(nK^2)$ 2
$O(n\lvert T \rvert^3)$ , because the dictionary does not change the dynamic program3
$O(K^n)$ , because every tag sequence must be scored4

Timed test