Return to Answer

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!).

And just how do you propose to find a maximum distance without computing every distance ? In other words, the answer to your question is that a correct understanding of the complexity of the algorithm provides you with a much more efficient solution than you thought you had, but that there is an irreducible minimum complexity when dealing with n^2 elements.

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!).

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!).

And just how do you propose to find a minimum distance without computing every distance ? In other words, the answer to your question is that a correct understanding of the complexity of the algorithm provides you with a much more efficient solution than you thought you had, but that there is an irreducible minimum complexity when dealing with n^2 elements.

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!).

And just how do you propose to find a maximum distance without computing every distance ? In other words, the answer to your question is that a correct understanding of the complexity of the algorithm provides you with a much more efficient solution than you thought you had, but that there is an irreducible minimum complexity when dealing with n^2 elements.

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^2) where k is the number of elements in the vector; this still gives a complexity well below O(n!).

And just how do you propose to find a minimum distance without computing every distance ? In other words, the answer to your question is that a correct understanding of the complexity of the algorithm provides you with a much more efficient solution than you thought you had, but that there is an irreducible minimum complexity when dealing with n^2 elements.

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!).

And just how do you propose to find a minimum distance without computing every distance ? In other words, the answer to your question is that a correct understanding of the complexity of the algorithm provides you with a much more efficient solution than you thought you had, but that there is an irreducible minimum complexity when dealing with n^2 elements.