  his study presents a novel technique to estimate the computational complexity
of sequential decoding using the Berry-Esseen theorem. Unlike the theoretical
bounds determined by the conventional central limit theorem argument, which
often holds only for sufficiently large codeword length, the new bound obtained
from the Berry-Esseen theorem is valid for any blocklength. The accuracy of the
new bound is then examined for two sequential decoding algorithms, an
ordering-free variant of the generalized Dijkstra's algorithm (GDA)(or
simplified GDA) and the maximum-likelihood sequential decoding algorithm
(MLSDA). Empirically investigating codes of small blocklength reveals that the
theoretical upper bound for the simplified GDA almost matches the simulation
results as the signal-to-noise ratio (SNR) per information bit ($\gamma_b$) is
greater than or equal to 8 dB. However, the theoretical bound may become
markedly higher than the simulated average complexity when $\gamma_b$ is small.
For the MLSDA, the theoretical upper bound is quite close to the simulation
results for both high SNR ($\gamma_b\geq 6$ dB) and low SNR ($\gamma_b\leq 2$
dB). Even for moderate SNR, the simulation results and the theoretical bound
differ by at most \makeblue{0.8} on a $\log_{10}$ scale.
