enter image description here

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.

Please help how to find TC4 and TC8.

What can be the final time complexity of this EM algorithm in terms of Big-O?

  • $\begingroup$ 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. $\endgroup$ – StasK Sep 19 '17 at 14:47
  • $\begingroup$ I have changed the algorithm's picture and added the meanings of C and N. And also I have added the link of this algorithm. Please take a look on it. @StasK $\endgroup$ – Justlife Sep 19 '17 at 15:20
  • $\begingroup$ Thanks -- again, if you are concerned with total computing time, the thing that it is going to bite you is convergence rate (e.g. dspace.mit.edu/bitstream/handle/1721.1/7195/…) $\endgroup$ – StasK Sep 19 '17 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.