What is the complexity of Mixture Hidden Markov Models (MHMM)?
Mixture hidden markov model is not one algorithm. It's made of forward algo, viterbi algo and forward-backward algo.

The time complexity of computing the forward variable used in hidden markov models is O(N2T) In which N is the number of states and T is the length of the observations sequence.