In terms of Big O notation what category is O(N*P), P signifying feature size, as seen in Naive Bayes or kNN?

user_9870489 0
Viewed 60

If time complexity of some of the machine learning algorithms such as; kNN and Naive Bayes can be defined as O(N*P) where N is number of rows and P is feature size, which Big O complexity does this count as?

Does O(N*P) time complexity fall in same category as O(N) hence is it "Linear Complexity"? If P=N was true couldn't it also be counted as O(N^2) hence Quadratic Complexity? So, exactly what complexity can we call it, is it undetermined? Thank you.

computation knn naivebayes machine-learning time-complexity
1 Answers

As you said, it depends on the value of P. Hence, the time complexity is O(N*P) in general, and you can explain it in more detail when we know more about the value of P. For another example than you have mentioned, if P = N^2, the time complexity can be Qubic as well. Therefore, you can't say anything about this time complexity without knowing about P.

user_37688710
Related