Computational complexity (aka time complexity) of an algorithm is the amount of time it needs to run as a function of the input size.
Questions tagged [time-complexity]
92 questions
29
votes
1 answer
k-NN computational complexity
What is the time complexity of the k-NN algorithm with naive search approach (no k-d tree or similars)?
I am interested in its time complexity considering also the hyperparameter k. I have found contradictory answers:
O(nd + kn), where n is the…
Daniel López
- 5,164
- 2
- 21
- 42
19
votes
1 answer
Machine learning classifiers big-O or complexity
To evaluate the performance a new classifier algorithm, I'm trying to compare the accuracy and the complexity (big-O in training and classifying). From Machine Learning: a review I get a complete supervised classifiers list, also a accuracy table…
Dinl
- 193
- 1
- 1
- 5
19
votes
2 answers
Speed, computational expenses of PCA, LASSO, elastic net
I am trying to compare computational complexity / estimation speed of three groups of methods for linear regression as distinguished in Hastie et al. "Elements of Statistical Learning" (2nd ed.), Chapter 3:
Subset selection
Shrinkage…
Richard Hardy
- 54,375
- 10
- 95
- 219
16
votes
2 answers
What is the time complexity of Lasso regression?
What is the asymptotic time complexity of Lasso regression as either the number of rows or columns grows?
user2763361
- 671
- 6
- 20
11
votes
1 answer
XGBoost paper - time complexity analysis
I'm reading through the XGBoost paper and I'm confused by the subsection of 4.1 titled "Time Complexity Analysis". Here the authors assert that the exact greedy algorithm with $K$ trees, a maximum depth of $d$ per tree, and $\|\mathbf{x}\|_0$…
Thom Lv
- 171
- 1
- 5
10
votes
1 answer
How does Lasso scale with the design matrix size?
If I have a design matrix $X\in\mathcal{R}^{n\times d}$, where $n$ is the number of observations of dimension $d$, what is the complexity of solving for $\hat{\beta}=\text{argmin}_{\beta}\frac{1}{2n} ||X\beta-y||^{2} + \lambda||\beta||_{1}$ with…
rnoodle
- 203
- 2
- 13
8
votes
2 answers
Why does my LSTM take so much time to train?
I am trying to train a bidirectional LSTM to do a sequential text-tagging task (particularly, I want to do automatic punctuation).
I use letters as the building-blocks: I represent each input letter with a 50-dimensional embedding vector, fed into a…
Erel Segal-Halevi
- 791
- 2
- 6
- 19
6
votes
3 answers
What is the computational cost of gradient descent vs linear regression?
I know the computational costs for the closed form of linear regression is $O(n^3)$, but I can't find a similar cost comparison to gradient descent.
There are some similar questions here with people "talk" about how gradient descent is more…
QuantStyle
- 61
- 1
- 1
- 2
6
votes
1 answer
Complexity of a random forest with respect to maximum depth
I expect the training time of a random forest to be : linear in the number of trees (obviously), linear (or square-root) in the number of columns (depending on the choice for the subsampling of the columns) and, when it comes to the maximum depth of…
RUser4512
- 9,226
- 5
- 29
- 59
5
votes
1 answer
Gaussian Process and Expectation Propagation time complexity?
What's the time complexity of training a Gaussian process and its Expectation Propagation approximation?
(Before studying them, I'd like to understand if they are even feasible for my application)
MWB
- 1,143
- 9
- 18
5
votes
2 answers
Do deep neural networks learn slower with the addition of more hidden layers?
The number of hidden layers increases the number of weights, also increases the terms in the back-propagation algorithm, i.e. more derivatives, hence more computation. Can we say that neural networks learns slower with the addition of more hidden…
The Limit Breaker
- 91
- 3
5
votes
1 answer
How to derive the time computational complexity of k-medoids (PAM) clustering algorithm?
I have read that the time complexity of k-medoids/Partitioning Around Medoids (PAM) is O(k(n-k)^2). I am trying to understand how this algorithms translates into this time complexity.
As per my assumption, we have to find the distance between each…
itkhanz
- 51
- 1
- 4
5
votes
1 answer
What is the computational complexity of the SOM algorithm?
Assuming $m$ observations, $n$ features and $k$ nodes in the self organizing map, what is the complexity of the classic SOM algorithm? What would be the complexity of an ensemble of SOMs, where each SOM has a different number of nodes?
GS9
- 233
- 1
- 3
- 7
4
votes
1 answer
Why Are Neural Networks Considered "Expensive" to Train?
Recently, I was looking at the optimization functions required in training Kernel Based Methods compared to Neural Networks.
1) Kernel Methods:
For instance, I was looking at the optimization in Support Vector Machines:
And Gaussian Process…
stats_noob
- 5,882
- 1
- 21
- 42
4
votes
1 answer
When does complexity in machine learning algorithms actually become an issue?
I keep seeing complexities for machine learning algorithms e.g. Gaussian process implementation requires inversion of an nxn matrix so complexity is $O(n^3)$.
When does complexity actually become an issue? Is there a way to work out when it becomes…
stochasticmrfox
- 1,125
- 4
- 14