Calculate the maximum distance between vectors in an array
algorithm, complexity-theory
Solution
Your computation of the naive algorithm's complexity is wonky, it should be `O(n(n-1)/2)`, which reduces to `O(n^2)`. Computing the distance between two vectors is `O(k)` where `k` is the number of elements in the vector; this still gives a complexity well below `O(n!)`.
Problem
Assume we have an array that holds n vectors. We want to calculate the maximum euclidean distance between those vectors. The easiest (naive?) approach would be to iterate the array and for each vector calculate its distance with the all subsequent vectors and then find the maximum. This algorithm, however, would grow (n-1)! with respect to the size of the array. Is there any other more efficient approach to this problem? Thanks.