I was wondering how to express the complexity of the Viterbi
Is it O(N2) or O(Nlog N) or is it exponential ?
I guess the complexity is linear with respect to the depth of the
trellis. A good description is given in "Digital Communications" by
> I was wondering how to express the complexity of the Viterbi
> Is it O(N2) or O(Nlog N) or is it exponential ?
It is exponential with the constraint length of the encoder. it is
function of 2^K where K is constraint length. Refer some digi comm
book for more detailed expression.
Hope this helps.
Thanks a lot for the replies.