# Questions tagged [time-complexity]

Computational complexity (aka time complexity) of an algorithm is the amount of time it needs to run as a function of the input size.

103 questions
Filter by
Sorted by
Tagged with
14 views

### What is the time complexity one-to-many LSTM? [closed]

What is the time complexity one-to-many LSTM ?
• 1
65 views

### Does training time increase more if I add a layer at the beginning of a neural network or at the end?

Let's consider a fixed NN architecture, dataset and hardware. We add a layer, either at the beginning or at the end of the NN. In which case the training time will increase more? Intuitively, I ...
• 17.7k
37 views

### Estimating test error from $X^TX$ and $X^Ty$

Suppose we've got a dataset with a very large number of samples (say, billions), and a smaller number of features (say, hundreds). To calculate the coefficients of a single a ridge regression model, ...
• 21
95 views

### What is the complexity to compute the sample entropy of a time series of length N?

background Some algorithms are linear in operations, so the number of operations to complete is $O \left(N\right)$, while others are quadratic $O\left(N^2\right)$, cubic $O \left(N^3\right)$, or non-...
• 9,165
1 vote
32 views

### Fast algorithm of ARIMA-GARCH model selection

I use ARFIMA(p, x, q)-GARCH(P, Q) models for time series forecasting and when I calibrate models for selection the best via BIC criteria, I use "slow" approach when I calculate BIC for every ...
• 234
32 views

### Time complexity of Bayesian Ridge Regression

What is the training and inference time complexity of Bayesian Ridge Regression (e.g. as implemented in sklearn) in terms of the number of samples n and the number of features d?
• 809
100 views

### Time Complexity of using the kernel trick on polynomial basis expansion

I have read that: If we have two feature vectors ${x = (x_1,x_2,…,x_D)}$ and $y=(y_1,y_2,…,y_D)$ and we do a degree d polynomial basis expansion to get $f(x)$ and $f(y)$, then to calculate the inner ...
9 views

### Time complexity of ranked batch-mode sampling query strategy

I am performing different Active Learning experiments using several query strategies. One of the query strategies is the "Ranked batch-mode sampling" from Python's modAL library, which is an ...
• 31
76 views

• 101
1 vote
336 views

### Stepwise model selection by AIC

I am learning about performing stepwise model selection by AIC and having some questions: What is the regularization parameter for step-AIC? In what way is forward step-AIC an evolution of univariate ...
• 51
1 vote
46 views

### How to estimate the time and memory requirement for Sparse and variational Gaussian Process (SVGP) with minibatch approach

I'm implementing Sparse and variational Gaussian Process (SVGP) using GPflow library using minibatches. I've been trying to search for details regarding the time and memory complexities e.g. from this ...
• 5,777
69 views

### What are some well-known unbiased estimator of regression coefficient besides OLS estimator?

Is there any other unbiased estimator of regression coefficient than OLS? For instance, one might consider using unbiased estimator with less computational cost (since OLS involves matrix inversion)?
41 views

3k views

### 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 ...
262 views

### 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 ...
• 1,625
182 views

568 views

### How to find the time complexity of an MLE based algorithm

How to calculate or what is the time complexity (big-Oh) for this method? Based on my understanding, MLE depends on number of datapoints, $N$ so time complexity for MLE is O(N). However, there are ...
• 231
1k views

### Why does forward selection only take $O(p^2)$ calls to the learning algorithm?

In http://cs229.stanford.edu/notes/cs229-notes-all/cs229-notes5.pdf pg 5, it states that forward search takes $O(p^2)$ (note the notes uses $n$ instead of $p$ for the number if independent variables). ...
• 705
167 views

### Computational Complexity of SPADE, GSP and others

Does anybody know the computational complexity of SPADE, GSP, FreeSpan and PrefixSpan algorithm. I would like to have a comparisson in between these algorithms.
39 views

• 239
1 vote
36 views

### Issues with training on a sample of training set?

I am training an SVM on highly imbalanced data. I have rectified this issue and my ML pipeline works just fine. I have allocated 70% of my dataset for training, however this takes an infeasible amount ...
• 111
1 vote
4k views

### Why does R take so much time to run auto.arima(). How can I shorten the calculation time? [duplicate]

I have been trying to run analysis and model a ts series of Natural Gas spot prices. With data provided by the Qandl API. The whole analysis was working fine, however, I experiences issues with the ...
• 13
66 views

### complexity of empirical estimator

Assume we have i.i.d. data $x_{1}, \dots, x_{n}$ from discrete distribution. Then, let's us consider empirical estimator: $$\hat{p}_{i} = \frac{ \sum_{j=1}^{n}1(x_{j}=i)}{n}$$ What is the ...
• 476
8k views

### What is the computational complexity of a 1D convolutional layer?

What is the complexity of a 1D convolutional layer?. I'm getting $\mathcal{O}(n \cdot k \cdot d)$, but in Attention Is All You Need, Vaswani et al. report that it is $\mathcal{O}(k \cdot n \cdot d^2 )$...
• 6,129
288 views

### Complexity associated with decision trees

According to the sklearn documentation on decision trees: The cost of using the tree (i.e., predicting data) is logarithmic in the number of data points used to train the tree. Could somebody ...
• 31
456 views

### Computational complexity in practice: predict execution time for a dataset

Suppose I know that the computational complexity of an algorithm is $\mathcal{O}(f(n))$ where $n$ is the sample size. Suppose I have two data sets with sizes $n_1$ and $n_2$. The data sets have no ...
• 66.2k
51 views

### (Teaching) references for computational complexity

Background: I am going to teach computational complexity (time complexity) within an introductory course in machine learning. I would like to gently introduce the notion of computational complexity ...
48 views

### Neural Networks and a catalogue of the number of floating point operations in various types of statistical and time series models

I recently came across this paper Green AI. In the paper they discussed using floating point operation (FPO) count during testing and implementation of Neural Networks (NNs) to compare the ...
• 2,011
1 vote
88 views

### How to compute largest values of random variables? [closed]

Suppose we have two discrete random variables and we want perform maximum operation to obtain the max PDF. We know that max of two independent random variables is: if Z = max(X,Y) ...
• 11
1 vote