Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
3 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 (...
1
vote
1answer
51 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 "...
0
votes
1answer
28 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-...
0
votes
1answer
68 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 ...
0
votes
0answers
14 views

Effect of dimensionality for time taken to cluster data with k-means

In a dataset if I have $N$ features and for k-means clustering it might take $T$ seconds. If the dimensionality increased to $2N$, how would the time taken to run k-means clustering increase?
0
votes
1answer
139 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 ...
0
votes
0answers
9 views

How to find difference in optimal results v/s result from Heuristic algorithm?

my question states my problem. In my case, I have a resource allocation problem. The optimal solution can be obtained by using the brute-Force (BF) method. However, I have designed two different ...
1
vote
0answers
82 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. ...
2
votes
1answer
1k 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 ...
0
votes
0answers
106 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 ...
1
vote
1answer
52 views

Clustering: Clique vs. Agglomerative with Complete-Link

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=\...
1
vote
1answer
960 views

What is the time complexity of spectral clustering and why is it so?

What is the time complexity of spectral clustering and why (mathematically speaking) is it so? What are possible existing alternatives to speed up the computations required by the algorithm?
5
votes
1answer
526 views

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 ...
0
votes
1answer
126 views

What all does the training time for a neural network include?

I recently developed a DNN model and I want to know what exactly is training time and what all steps are included in it? For ex I carried out the following steps: Determined best Network ...
2
votes
0answers
294 views

GMM EM algorithm complexity per iteration

I was fitting GMM clusters with diagonal covariance on my data using EM with $n$ (=5e6) points, each having $m$ (=160) ...
1
vote
1answer
127 views

Dimension reduction methods: overview of complexity

For classical dimension reduction methods (PMF, PCA, SVD, t-SNE...) or some others, I need to know the complexity of efficient implementations: with $N$ vectors in dimension $d$ reduced to dimension ...
2
votes
0answers
139 views

Why is matrix notation in linear regression best way to compute coefficients?

I would to find the parameters for $y_i=\beta_0+\beta_1x_{1i}+\beta_2x_{2i}$ using the least squares concept and want to prove that matrix notation is computationally more convenient than my way below ...
1
vote
2answers
772 views

How can the xor function be formed with a single hidden layer of neural network?

I was recently viewing Andrew Ng's deep learning specialization lectures and I came forward to the following image It is pretty obvious how the above function( x1 XOR x2 XOR x3..... XOR xn) can be ...
1
vote
1answer
197 views

Where does the exponential time complexity in LDA's posterior of topics arise?

In Finding scientific topics (PNAS 2004) the authors derive the (marginalized) posterior distribution of topic assignments given the observed word and arrive at equation (4). Then, immediately after, ...
1
vote
0answers
112 views

Real using of the “Realized GARCH” for 1 minute forecast

I would like to ask someone who has an experience with the "Realized GARH" by Peter Hansen. I have 2 questions: Is there a logical purpose to use realGARCH for 1 minute forecast? How long could it ...
0
votes
0answers
347 views

Time complexity of the EM algorithm

this is Fuzzy Relational Eigenvector Centrality-based Clustering Algorithm (FRECCA). Here, N = total number of data, C is the number of clusters. Link of this algorithm is here For line 1-10, time ...
1
vote
2answers
733 views

Why are k-means and k-NN considered simple algorithms in machine learning?

We all know the k-means clustering algorithm and the k-nearest neighbors algorithm: the former is an unsupervised clustering method, and the latter is a supervised learning technique in machine ...
0
votes
1answer
210 views

Time Complexity Pooling Layers

What is the big oh complexity of Keras' GlobalMaxPooling1D() layer? More generally, how would you find the complexity of pooling layers?
2
votes
0answers
29 views

“Wrong polarity” of SVM in Bottou & Lin (2006)

I am reading the paper "Support Vector Machine Solvers" by Bottou and Lin (2006). On page 10, the authors engage in a discussion about the asymptotic number of support vectors as a function of the ...
0
votes
1answer
1k views

What is the time and space complexity of single linkage hierarchical clustering?

I have read everywhere that the time complexity of hierarchical agglomerative clustering is $\mathcal{O}(n^3)$ and it can be brought down to $\mathcal{O}(n^2 \log n)$. How do we arrive at such ...
0
votes
1answer
420 views

can the time complexity of k-nearest-neighbor allow it to be used as a clustering technique?

If I have N of about 3000 data points, each of about dimensions d of 50, and so the k in kNN is sqrt(3000/2) is about 40, then applying kNN to these points would be about O(NdK) = O(3000*50*40) which ...
10
votes
1answer
476 views

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} |...
1
vote
1answer
822 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 ...
4
votes
0answers
107 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 ...
2
votes
0answers
1k 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 ...
0
votes
0answers
95 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 ...
1
vote
0answers
156 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?...
2
votes
0answers
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 ...
0
votes
1answer
224 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 ...
1
vote
1answer
74 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?
0
votes
0answers
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 ...
5
votes
1answer
1k 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 ...
15
votes
1answer
28k 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 ...
3
votes
1answer
560 views

Computational complexity of the lasso (lars vs coordinate descent)

The lasso can be computed with the LARS or Coordinate Descent algorithm. What is their computational complexity and when one is quicker than the other?
3
votes
1answer
147 views

Reference summarizing various machine learning algorithms' computational complexity

For example, suppose you train a linear regression model using the Normal Equation, on a training set $\mathbf{X}$ containing $m$ instances and $n$ features. The Normal Equation requires computing $(\...
2
votes
0answers
247 views

How to determine time complexity of EM algorithm of probabilistic PCA?

I was studying probabilistic PCA from Bishop's book. There an EM algorithm is provided to calculate principal subspace: Here $\mathbf M$ is $M\times M$ matrix, $\mathbf W$ is $D\times M$ matrix and $...
2
votes
0answers
147 views

Which non-parametric multiple-regression methods are computationally efficient with respect to the number of regressors?

I did some regression in R with random forests and got some decent results, $1-\sum{|e_i|}/\sum{|y_i-\bar{y}|}=0.692$, but I want to do better than this. Through my research, I have concluded that the ...
2
votes
1answer
2k views

Comparison of LDA vs KNN time complexity

Which algorithm has a better performance in terms of time complexity, LDA or KNN?
18
votes
2answers
1k views

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.), ...
1
vote
1answer
4k views

Why is clustering data with many categorical variables so slow?

I am trying to cluster a set of 160 points using 260,000 categorical variables (each variable has three possible values). I am trying to use the k-modes algorithm from the klaR package in R. It works ...
2
votes
0answers
57 views

How is it computationally possible to calculate ANOVA of microarrays with interactions of 4000 genes and 7 times

M. Kerr and G. Churchill use ANOVA to separate changes in gene expressions from effects due to the used arrays or dye using the interaction terms time*gene As they are dealing with yeast which has ...
3
votes
1answer
549 views

Comparing 2 sets of longitudinal data

Blood level of a chemical was recorded in children of different ages in 2 studies. Means and variance is available for different ages as shown in following manually created figure: I can compare two ...
5
votes
1answer
2k views

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 ...
3
votes
1answer
2k views

Computational complexity for linear discriminant analysis

The linear discriminant analysis algorithm is as follows: I want to conduct a computational complexity for it. For each step, the complexity is as follows: For each $c$, there are $N_cd$ additions ...
0
votes
0answers
89 views

Parametrizing a matrix (and algorithm) by its orthogonal complement

Given a large orthonormal matrix $U$, say $p\times p-k$ (with $k$ much smaller than $p$), is there an effficient way to parametrize $U$ by any matrix orthogonal complement (any orthonormal matrix ...