Time complexity Question

#1

Why in k-NN algorithm, if euclidean distance is used as a distance metric, then execution completes in 2 mins and if wminkowski is used as distance metric, it takes 52 min for the same algorithm to execute?

#2

hi @ankita23 this is a ML related doubt, please ask it under the relevant course so that the TAs can assist you.

#4

hi @ankita23 this is not relevant to the contents taught in your course, i’d strongly suggest you to ask it under the approriate section for better assistance.

#6

@ankita23 you can refer to these:
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4978658/
https://towardsdatascience.com/how-to-measure-distances-in-machine-learning-13a396aa34ce

#7

can you give me the information of the TA who is taking ML course ?

#8

It would be better if he knows concept of time complexity as well

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#11

hello @ankita23
image

image

here u can see that minkowsky is more calculation instensive when compared to euclidian disctance , so this may be one of the reason why this happens ->

#14

I don’t think it’s because of the formula. Any other reason? I think inbuilt function is written in that way. Any insight regarding that?

#15

MY DOUBT IN DETAIL:

While executing k-NN on a large dataset containing around 1,68,000 records using the inbuilt function available in Python for prediction of continuous values, Euclidean distance takes 2 mins whereas if I use wminkowski distance as a distance metric for computing distances between two instances, k-NN is executed in around 52 minutes. Out of 1,60,000 records, 70% were used for training and 30% were used for testing. The training was taking almost no time and testing was taking all the time. So, to test 50400 records, 52 minutes was taken if I used wminkowski as a distance metric but Euclidean distance took only 2 minutes.

Can you please explain the reason behind such vast time difference? Are there any means by which time complexity of wminkowski can be used?

#16

inbuilt function also takes time as they are also running some algorithm.

#17

u should take help from some machine learning expert, as there can be some other reason as well .

#20

Give me the contact of any machine learning expert who can clear my doubts in best way.

#21

please help me in this regard

#22

hey i dont have anyone contact no .
you can ask it in ur whatsapp group someone from ml domain might help u.

#23

you know any TA from ML domain who might help?

#24

u can contact vasu gupta.

#25

Can u forward my question to him?

#26

i dont know him personally.
u can directly dm ur doubt to him

#27

I also don’t know him and i don’t have any of him contact too. so where should I dm?