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

95 questions
Filter by
Sorted by
Tagged with
1 vote
23 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 ...
1 vote
12 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 ...
37 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)?
23 views

### Computational Complexity of Gradient Boosting Decision Tree algorithm

Does anybody have an idea about the computational complexity of GBDT? I have only seen one paper report (Gradient Boosted Decision Trees for High Dimensional Sparse Output). It doesn't seem to be ...
15 views

### Why does the slow version of TreeExplainer algorithm have a complexity of $TLM2^M$

I'm trying to understand the TreeExplainer algorithms better from From Local Explanations to Global Understanding with Explainable AI for Trees, but confused by how the time complexity is derived even ...
26 views

71 views

### Time complexity of training SVM and C

I always though that a big (high) C will lead to a lower svm training complexity due to lower number of support vectors. I was very surprised to read a paper that states the opposite - aka, big Cs ...
27 views

### Expected value of log-likelihood and KL divergence

Background: Let $x_t = Ax_{t-1} + w_t$ be a discrete linear time invariant system where: $x_t \in \mathbb{R}^d$ for all time samples $t$ corresponds to the state vector $A\in \mathbb{R}^{d\times d}$ ...
1 vote
32 views

### FLOPS calculation for deep architectures [duplicate]

Pleas guide me as I have exhausted all my efforts to do so. I need to have the FLOPS value for DeepID2+ which is an FR model and maybe a few more (DeepID, Deep Id2). No publication mentions it and I ...
9 views

I am working with a deep learning based system where complexity has to be reduced to a minimal. However, this is having some impact on the accuracy. I am having to ask the question in somewhat ...
8 views

1 vote
3k 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-...
729 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 ...
1k 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 ...