What is the complexity of dist()?

Question

I used the dist function in R and I am wondering the time complexity of it.

I know that the hierarchical clustering has a N^2*logN time complexity. And hierarchical clustering is composed of two parts as below codes in R.

> d <- dist(as.matrix(mtcars))   # find distance matrix 
> hc <- hclust(d)                # apply hirarchical clustering 
> plot(hc)                       # plot the dendrogram

before applying hierarchical clustering, calculating the distance matrix is required. I think this takes N^2 complexity?

The `hclust` function supposedly has O(n³) runtime. – Has QUIT--Anony-Mousse Jun 16 '17 at 07:26 — Has QUIT--Anony-Mousse, Jun 16 '17 at 07:26

Zheyuan Li · Accepted Answer · 2017-06-15T12:00:46.127

4

Precisely, if matrix X has N rows P columns, the complexity of dist(X) is 3N(N-1)P/2. This is computed by N(N - 1)/2 * 3P.

Explanation:

There are N(N - 1)/2 entries in the resulting distance matrix;
Each entry is a dot product between two length P vectors (plus a square root), each involving P subtraction, P multiplication and P addition.

edited Jun 15 '17 at 12:00

answered Jun 15 '17 at 11:52

Zheyuan Li

71,365
17
180
248

if `N`==`P`, then you mean it take `N^3`? – sclee1 Jun 15 '17 at 11:56
As far as my understanding goes, big O is all about when N gets very big and other parameters stay the same. So I think this is actually O(N^2). – Christopher John Nov 28 '18 at 14:07
Why Cluster algoritms like CAH or Gower has O(N^3) but they have N and P parameters? – abdoulsn May 14 '20 at 16:29

What is the complexity of dist()?

1 Answers1