  This paper investigates guesswork over ordered statistics and formulates the
complexity of ordered statistics decoding (OSD) in binary additive white
Gaussian noise (AWGN) channels. It first develops a new upper bound of
guesswork for independent sequences, by applying the Holder's inequity to
Hamming shell-based subspaces. This upper bound is then extended to the ordered
statistics, by constructing the conditionally independent sequences within the
ordered statistics sequences. We leverage the established bounds to formulate
the best achievable decoding complexity of OSD that ensures no loss in error
performance, where OSD stops immediately when the correct codeword estimate is
found. We show that the average complexity of OSD at maximum decoding order can
be accurately approximated by the modified Bessel function, which increases
near-exponentially with code dimension. We also identify a complexity
saturation threshold, where increasing the OSD decoding order beyond this
threshold improves error performance without further raising decoding
complexity. Finally, the paper presents insights on applying these findings to
enhance the efficiency of practical decoder implementations.
