can the time complexity of k-nearest-neighbor allow it to be used as a clustering technique?

Question

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?

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!