What is the computacional complexity in asymptotic notation, O(n) , for the function "pdist2" ?

What is the computacional complexity in asymptotic notation, O(n) , for the function "pdist2" ?

Answer 1

[Walter Roberson]

With a vector of length L, each pair of values has L subtractions, followed by L squaring (each is one multiplication), followed by L-1 additions, followed by one square root. So far this is independent of the number of entries in the matrix, so for any given L, the time is constant.

The number of pairs of distances is N * (N-1) / 2

Therefore pdist2() is O(N^2)