pdist time complexity and inner working

What is the time complexity of pdist, how does it calculate different distances between sets of points?

The documentation for pdist does not include anything about the complexity and its internal workings, could someone please guide me as to where to find this information.

Thank you in advance.

Answer 1

[Walter Roberson]

You can read the source code.

For most of the distance measures a loop is done over elements of the array, picking out a particular point and calculating the distance to the remaining points after it. So (N-1) distances the first time, then N-2 for second iteration, then N-3 and so on down to 1. Time is the sum of those, 1 to N-1, which is N*(N-1)/2 which is O(N^2)

You might possibly want to define it more strictly as O(d*N^2) where d is the dimension of the points.

There are no advanced algorithms involved. No quadtree, for example, that might hypothetically reduce the number of comparisons for cityblock to lower than d (the dimension). No removal of duplicate locations is done (detection of duplicates would be O(n*log(n)*d) and you would still need O(N^2) after)

[Ashish]

Thank you so much!. where can I find the source code and more information regarding pdist?

[Walter Roberson]

edit(which('pdist'))