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

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
123 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 ...
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 ...
181 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 ...
342 views

40 views

### sample complexity vs training cost (time complexity)

I have a question about the complexities. Consider two regression problems A, B and assume that A has lower sample complexity than B. A and B share the same target function but the loses are slightly ...
23 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 ...
84 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 ...
996 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 ...
207 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 ...
223 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?...
8 views

9 views

652 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 ...
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 ...
670 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 ...
103 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 ...
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 ...