A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

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

63 questions
Filter by
Sorted by
Tagged with
146 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 )$...
19 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 ...
16 views

### applying fast Fourier transform without restriction on N

I want to apply fast Fourier transform for a sequence of complex numbers with length N. N can be anything (not necessarily a power of 2). It seems that Cooley–Tukey algorithm only works for the ...
40 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 ...
28 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 ...
12 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 ...
77 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) ...
136 views

### Time complexity of batch gradient descent

I am read http://papers.nips.cc/paper/4937-accelerating-stochastic-gradient-descent-using-predictive-variance-reduction.pdf paper. It states that "Due to the poor condition number, the standard batch ...
42 views

### knn asymptotic complexity vs svm [duplicate]

I'm doing a little report about the KNN complexity vs SVM.. I would like to know your opinions.. I built this text according to my perspective searching in papers, websites, ppts etc: The reason ...
81 views

### Who is more complex computationally knn or SVM? [closed]

I have trained two models using sklearn library in python.. My dataset was about 750 features, 250 features per class (three classes), I trained only one feature dimension (1-D array). This are the ...
23 views

### Time complexity for locality sensitive hashing similar image search

I am trying to find most visually similar images for large image dataset. (N=1 million), using LSH (Locality Sensitive Hashing). Image feature vectors are 4096 dimensional VGG-16 features. Now, my ...
32 views

### What are the time complexity of image feature extraction algorithms, including HS, HOG, MSER and SIFT?

Can somebody help me by writing me a time-complexity of each image feature extraction algorithms. Especially I am interested in Harris-Stephens(HS) corner detection, Maximally Stable Extremal Regions (...
1k views

### 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 "...
344 views

### What does it mean for K mean problem to be NP hard and why?

Given a decision problem (a problem with yes or no answer), the problem is said to be NP-hard if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time. Recall that NP-...
182 views

### How to inform the space and time complexity of K-means, SOM and Hierachical clustering

In the paper I am writing, one of the reviewers asked for an "a simple computational complexity analysis or time computational demands of their method" My question is : Can I simply report the ...
241 views

### K means clustering time fluctuates with increased value of K

I have written k means clustering code in c#. I am clustering random 99 text articles of Sports Area which I downloaded from Github for different values of K i.e.3,4,5,6,7. I want to analyze the time ...
156 views

### Computational complexity of sampling from discrete and continuous distributions?

What is the computational complexity of sampling from any of these cases? I mean the computational complexity of the most efficient existing algorithm, not a possible algorithm or a lower bound. ...
4k views

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

### Computational complexity of MaxiEnt classifier

I know that the time complexity of logistic regression can be as low as linear when the optimizer/solver is assumed to be linear, such as L-BFGS (this link) I know that multinomial logistic regression ...
73 views

969 views

### Supervised Machine learning classifiers big-O [closed]

I'm comparing different machine learning for classifying sensor data and I need their complexity to select the most efficient. Which are the Big-O notation for the following algorithms (I add what I ...
113 views

### What is the feasibility to run linear model for large amount of data?

I am looking for empirical approximations and guidelines on how many operations are required to run a linear model on a given amount of data, or if it's even feasible. Let's assume we use QR ...
2k views

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

### The relation of time-series signals complexity and other statistical and signals processing concepts

What is the relation between correlation and time-series signal complexity? For example, I was reading a paper that is talking about the Multi scale entropy (MSE) and its advantages over the Shannon ...
189 views

### What are the computational complexities of Linear One-vs-One, Bayesian Multivariate, and k-NN algorithms?

What are the computational complexities of Linear One-vs-One Committe, Bayesian multivariate with the class independence assumption, and k-NN algorithm with k=3? In $\mathcal{O}$ (Big-O) notation?...
39 views

### Algorithmic Complexity of Estimators

I am interested in evaluating the algorithmic complexity of an estimator of the form: $$\hat{\theta} = \text{argmin}_{\theta} \;\; Q_n (\theta)$$ where $Q_n(\theta)$ denotes some objective function ...
486 views

### How can one estimate compute requirements for Machine Learning algorithms?

Has anyone developed formulas or rules of thumb for estimating CPU, memory and time requirements for running various Machine Learning algorithms (or families of algorithms), with respect to training ...
112 views

### Effect of training data on complexity of kernel

How does the amount of training data affect the complexity of a linear kernel in support vector machine?
28 views

### weighing of probabilities in a multi horizon framework

I shall start with an example so it's clear what I'd like to explore: I have to decide how many sigarettes to smoke in a day. One person tells me they will me kill should it rain. his credibility ...
2k views

### 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 ...
35k views

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