Hello Everyone I am studying the time complexity of different clustering
algorithms, and the fast greedy algorithm is claimed to be very fast. That is,
for n vertices, the time complexity is O(m d logn),m is the number of edges and
d is the depth of dendrogram, and for a sparse and hierarchical matrix d ∼log n
and m ∼ n so the complexity is O(n log2 n). There are a lot of papers analyzing
time complexity of Ward method, and the results are usually O(n3) for worst
cases and O(n2 logn) or O(n2) for best cases. But what is the actual complexity
of the 2 algorithms? In my understanding, depth of dendrogram is the number of
joins. When applying the fast greedy to a 39*39 non-sparse matrix there are 39
joins, that is d=39, and there are 39*(39-1)/2 edges, that is m=39*(39-1)/2.
Let n=39, so the time complexity is O(n*n*(n-1)* logn /2), which is better than
(n3), but the practical running time of fast greedy is much shorter than Ward
method for a same 39*39 non-sparse matrix( 0.000718 sec vs 0.080318,almost
1:30). The theoretical ratio when n=39 should be 1:3, instead of 1:30. So what
is the key to the results and what is the real time complexity of fast greedy
and Ward method? Thank you.
_______________________________________________
igraph-help mailing list
igraph-help@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help
