In general, and more specifically for Bernoulli mixture model (aka Latent Class Analysis).
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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  see 3.1 . Some of these problems are proved to be NP-hard, whether with EM or not. See [3,4].