# Why exhaustive search grows exponentially

Subject: Natural Language Processing

Exam: M2

Reader: https://deep-learning-study-room.vercel.app/nlp/#m2/formulas/f-hmm/sequence-count

Canonical: https://deep-learning-study-room.vercel.app/read/nlp/m2/formulas/f-hmm--sequence-count/

Formulas explained through full worked examples

If each of T observed words can receive any of N tags, there are N choices at each position. Thus the total number of complete tag sequences is N multiplied by itself T times. This counts possible assignments before grammar rules or zero probabilities eliminate any.



$$
\text{Number of tag sequences}=N^T
$$



**Question. A four-word sentence is tagged using three possible POS tags per word. How many complete tag sequences are possible?**

#### Given

N=3 possible tags per position; T=4 word positions.

#### To find

The number of tag sequences.

#### Formula and why it applies



$$
M=N^T
$$



Every independent position contributes a factor of three choices.

#### Solution

##### Step 1. Write one factor per position



$$
M=3\times3\times3\times3
$$



##### Step 2. Multiply



$$
3\times3=9,\quad9\times3=27,\quad27\times3=81
$$



**Final answer.** 81 possible tag sequences.

**Question. A five-word sentence has two candidate tags per word. Count its tag sequences.**

#### Given

N=2; T=5.

#### To find

M.

#### Formula and why it applies



$$
M=N^T
$$



The length is the exponent, not a multiplier.

#### Solution

##### Step 1. Substitute



$$
M=2^5
$$



##### Step 2. Evaluate



$$
2\times2\times2\times2\times2=32
$$



**Final answer.** 32 possible sequences.

**Question. Using 45 possible tags, compare the number of tag sequences for sentences of length 2 and 3.**

#### Given

N=45. First T=2, then T=3.

#### To find

Both counts and the growth factor.

#### Formula and why it applies



$$
M_2=45^2,\quad M_3=45^3
$$



Adding one position multiplies the possibilities by the number of tag choices.

#### Solution

##### Step 1. Two words



$$
45^2=2025
$$



##### Step 2. Three words



$$
45^3=2025\times45=91125
$$



##### Step 3. Compare



$$
91125/2025=45
$$



**Final answer.** 2 words: 2025 paths. 3 words: 91125 paths. One additional word multiplies the count by 45.

The slides introduce Viterbi to avoid enumerating every path. It reuses the best prefix score for each ending state. For a dense first-order HMM, it needs O(TN²) recurrence work instead of enumerating NT complete paths.

**Yaad rakho:** Choices per word ki power = sentence length.