How to implement hierarchical clustering in $O(N^2)$ instead on $O(N^3)$ First a theoretical question. I know that natively, an hierarchical clustering algorithm is of complexity on the cube of number of samples N. This is due to the fact that in each iteration, one has to go over the entire distance matrix to find the smallest value. 
But, it is possible to implement it in lower complexity (of N square). How it is done and can you refer me to an article or description of the implementation? 
Finally, I used scikit library to do HClustering. It was fine but it is limited to 15,000 samples or so. I want to cluster much more. can someone refer me to an implementation that fits larger numbers (and preferably runs at square root N)?
 A: As far as I know, this is not generally possible, but algorithms only exist for particular linkages; i.e. SLINK for single-link and CLINK for complete-link.
ELKI includes an $O(n^2)$ implementation, i.e. SLINK.
If I understood SLINK correctly, it essentially works "one row at a time", which is why it also needs less (linear!) memory.
A: This is simply to answer the last part of your question (cannot run HClustering on more than 15,000 samples).
If you really want to do a hierarchical clustering (for interpretation), I would suggest running kmeans (that will run quite fast with scikit) with a high k-value (for example 1000 or 100). Then, you run the HClustering on the resulting centroids to have a global clustering. (and you can reassign each point to its centroid and then to its cluster).
A: Clink and slink has time complexity of o(n2), but I don't understand how in clink and slink after merging two clusters they find the distance of that merged cluster from the new clusters .If they directly compute, then worst case time complexity should be
(n-1)+2(n-2)+3(n-3)+4(n-4)+.....(n-1)(n-(n-1)) =O(n3).
