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

92 questions
Filter by
Sorted by
Tagged with
8 views

1k 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 ...
9 views

3k 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 )$...
82 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 ...
192 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 ...
42 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 ...
24 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 ...
83 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) ...
994 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 ...
236 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 ...
514 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 ...
13k 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 "...
2k 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-...
643 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 ...
968 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 ...
710 views

### Computational complexity of sampling from discrete and continuous distributions? [closed]

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. ...
13k 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 ...
217 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 ...
In my data, I have a defined a symmetrical relation $R$ where $R(i,j)=R(j,i)$ indicates that $i$ and $j$ are closed each other. I need to find cliques $C_1,C_2,\dots,C_n$ where \$C_k\cap C_l=\...