Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Viterbi Algorithm › Complexity Analysis

Michael BrenndoerferUpdated April 28, 20254 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 41Viterbi Algorithm › Complexity Analysis

Reading section 6 of 12 · Complexity Analysis · 4 minSection 6 of 12 · 4 min

Section 6 of 12 · 4 min read

Viterbi Algorithm › Complexity AnalysisOne section · Sections in this chapter6 / 12 ↓

Sections in this chapter12

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

The Viterbi algorithm's efficiency comes from its dynamic programming structure. Let's analyze the time and space requirements.

Time ComplexityLink Copied

For a sequence of length $n$ with $k$ possible states:

Initialization: $O(k)$ operations to set up the first column
Recursion: For each of the $n-1$ remaining positions, we compute $k$ cells. Each cell considers $k$ predecessors. Total: $O(n \cdot k^2)$
Backtracking: $O(n)$ to trace back through the path

The overall time complexity is $O(n \cdot k^2)$ , which is linear in sequence length and quadratic in the number of states.

In[15]:

Code

import time


def benchmark_viterbi(seq_lengths, n_states_list):
    """Benchmark Viterbi performance."""
    results = []

    for n_states in n_states_list:
        for seq_len in seq_lengths:
            # Create synthetic HMM
            states = [f"S{i}" for i in range(n_states)]
            obs = [f"O{i % 5}" for i in range(seq_len)]

            # Uniform probabilities for benchmarking
            start = {s: 1 / n_states for s in states}
            trans = {(s1, s2): 1 / n_states for s1 in states for s2 in states}
            emit = {(s, f"O{j}"): 0.2 for s in states for j in range(5)}

            # Time the algorithm
            start_time = time.perf_counter()
            for _ in range(3):  # Average over 3 runs
                viterbi_log_space(obs, states, start, trans, emit)
            elapsed = (time.perf_counter() - start_time) / 3

            results.append(
                {
                    "seq_len": seq_len,
                    "n_states": n_states,
                    "time_ms": elapsed * 1000,
                }
            )

    return results


# Run benchmarks
seq_lengths = [10, 50, 100, 200]
n_states_list = [5, 10, 20]
benchmarks = benchmark_viterbi(seq_lengths, n_states_list)

Out[16]:

Console

Viterbi Algorithm Benchmarks
=======================================================

Seq Length   States     Time (ms)   
-------------------------------------------------------
10           5          0.048
50           5          0.192
100          5          0.379
200          5          0.808
10           10         0.129
50           10         0.644
100          10         1.206
200          10         2.447
10           20         0.461
50           20         2.244
100          20         4.465
200          20         8.836

The benchmarks confirm the theoretical complexity. Doubling sequence length roughly doubles runtime (linear scaling), while doubling the number of states roughly quadruples runtime (quadratic scaling). Even with 20 states and 200-word sequences, Viterbi completes in tens of milliseconds, enabling real-time tagging in production systems.

Out[17]:

Visualization

Two line plots of relative Viterbi operation counts. The left plot rises linearly with sequence length, while the right plot rises quadratically with the number of states. — Deterministic operation-count proxy for the Viterbi algorithm. Left: work grows linearly with sequence length for a fixed number of states. Right: work grows quadratically with the number of states for a fixed sequence length. The proxy follows the theoretical n × k² recurrence and complements the environment-dependent timing table above.

Space ComplexityLink Copied

The algorithm stores:

Viterbi table: $O(n \cdot k)$ scores
Backpointers: $O(n \cdot k)$ references

Total space is $O(n \cdot k)$ . However, if we only need the final path and not the full table, we can reduce space to $O(k)$ by keeping only two columns at a time, though we'd need to run a second pass to recover the path.