# Time complexity of the EM algorithm

this is Fuzzy Relational Eigenvector Centrality-based Clustering Algorithm (FRECCA). Here, N = total number of data, C is the number of clusters.

Link of this algorithm is here

For line 1-10, time complexity(TC1) = (C+C)*N = 2CN

For line 11-13, TC2 = C

For line 18-22, TC3 = N*N

For line 24-26, TC4 = ?

For line 16-29, TC5 = (TC2+TC4) * C

For line 31-35, TC6 = NCC

For line 38-40, TC7 = C*N

For line 14-41, TC8 = TC5 + TC6 +TC7

Final Time complexity = O(TC8)

I am not sure what I am done is it correct or wrong. If it is not correct, please correct me.

And I do not understand how to calculate/represent the "repeat until convergence" condition.

• Rewrite the whole thing, please @Justlife. What is $C$, what is $N$? You pasted a very specific implementation of the EM algorithm to one specific problem, without even trying to explain what the problem is: the EM algorithm is a very generic way to deal with missing data, not just some pseudocode. Statisticians are aware of the notoriously slow linear convergence rates of the EM algorithm, vs. quadratic rates of Newton-Raphson, so computational complexity of a single step may not be that relevant if you have to take hundreds of these vs. a dozen or so by a different method. – StasK Sep 19 '17 at 14:47