Which algorithm has a better performance in terms of time complexity, LDA or KNN?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ This seems like it should be perfectly answerable to me. $\endgroup$– gung - Reinstate MonicaMay 6, 2016 at 10:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Time complexity depends on the number of data and features.
LDA time complexity is $O\left(Nd^{2}\right)$ if $N>d$, otherwise it's $O\left(d^{3}\right)$ (see this question and answer). It's mostly contained in the training phase, as you have to find the within class variance.
k-NN time complexity is $O\left(Nd\right)$. Actually, training without preprocessing is instantaneous (check this book), testing takes most time as you have to compare each test instance to most (or even the whole) training data.
Said that, without any other optmizations, k-NN should run incrementally faster than LDA as you add more dimensions to your problem.
Also, k-NN time complexity is pretty much insensitive to the number of classes in most implementations. LDA on the other hand has a direct dependence on that.
