If I have N of about 3000 data points, each of about dimensions d of 50, and so the k in kNN is sqrt(3000/2) is about 40, then applying kNN to these points would be about O(NdK) = O(3000*50*40) which doesn't seem bad.

I've heard that kNN is very susceptible to the curse of dimentionality, but

Question = if I use it as a clustering technique, thus grouping similar data points together, for fixed k, then wouldn't I efficiently be able to implement it for this case?

Question = what are other similar clustering techniques possibly with more efficient time complexity?


1 Answer 1


At 3000 data points, runtime is not an issue (usually, depending on code quality). You can afford to use HAC with O(n³). Others are working with millions of points.

Also, you understanding and use of O notation indicates you have not understood it well. It is a notion that solely applies to laaaaarge n. A method that is in O(n³) can be faster than one in O(n²) for any "small" n such as n=100000, because of the omitted terms. This notation applies to the worst-case performance of near-infinite data only. Which is why this notion is rather useless outside of theory, unfortunately. Never ever put in real numbers. Never!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.