Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In general, and more specifically for Bernoulli mixture model (aka Latent Class Analysis).

share|improve this question

I do not think you can compute the complexity in the usual way. How long it takes the EM algortihm depends on the starting point, the shape of the likelihood and the stopping criterion.

share|improve this answer
You can do the computational cost per iteration, though. Of course, for a given problem there might be different ways of implementing the same EM procedure with different computational complexities. – guy Nov 7 '13 at 3:21

I liked your question!

The complexity of EM depends on the structure it is being applied on, and could be quite different from one problem to another one. But, just like any computational problem, it might be worthy of rigorous analysis to find and compare the complexity in different cases.

For some of the problems it is analyzed. For example in [1] see 3.1 . Some of these problems are proved to be NP-hard, whether with EM or not. See [3,4].

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.