# Questions tagged [complexity]

Relating to the level of difficulty of a calculation or the asymptotic running time of an algorithm.

107 questions
Filter by
Sorted by
Tagged with
1k views

### Why is it that SVD routines on nearly square matrices run significantly faster than if the matrix was highly non square?

In Python / Matlab, if you run a routine for SVD on a significantly non-square matrix, X, such as X.shape = (2,15000) you will ...
• 203
1 vote
129 views

### Is OCN=DOCN decidable or not?

One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that cannot decrease below zero and cannot be explicitly tested for zero. An OCN $A$ over alphabet $\sum$ accepts a ...
• 11
95 views

### Algorithm about finding a combination that the sum is closest to a given number

Given a matrix $P\in \mathbb{R}^{n*k}$ (just for ease of notation, no matrix or linear algebra is actually needed; bound to $(0,1)$ if necessary), select one number from each row and compute the sum. ...
• 141
1 vote
143 views

### Space complexity of a semidefinite program

What is the space complexity of a semidefinite program (SDP)? What is the answer to the same question for convex optimization problems in general?
186 views

### Complexity of Branch-and-cut algorithm in terms of "Big O"

How can I compute the Big O complexity of the Branch and cut algorithm? I am solving an integer linear program using MOSEK that includes $M$ binary variables, but I do not know how to calculate the ...
324 views

### Complexity of recovering all roots of a polynomial

Given a polynomial of degree n and a list of putative roots $\{r_i\}_{i=1}^{n}$, we can verify that all the putative roots are indeed correct by $n$ applications of Horner's method. Hence verifying ...
• 2,145
75 views

### Eigen-decomposition one eigenpair by one eigenpair?

Is it possible to conduct an Eigen-decomposition of a matrix one eigenpair by one eigenpair? And related to this question, what is the time complexity of truncated eigendecomposition? I am trying (...
• 109
91 views

### Worst Case complexity of a search engine algorithm

Computer make it possible to find information in large databases. However, the results are often too large to be returned in their entirety to the user who requests them. Computer therefore sort the ...
62 views

### Is there a unit of measure for computational complexity; through quantum computers? [closed]

I'm concerned with trying to determine whether the same computational processes on a Turing computable algorithm can be ascertained for a quantum computer in some form of actual 'metric' for how many ...
62 views

### Comparison of computational complexities of MD versus MC simulations

In my humble understanding MD simulations of systems with short-range(like LJ interactions) and long-range(electrostatic) has a computational complexity $O(N . log(N))$. What will be the computational ...
6k views

### Why are log and exp considered 'expensive' computations in ML?

In many resources/videos I see comments being made along the lines of "and we can see here that we have a logarithm/exponential so this will be an expensive computation to make." (such as ...
• 173
318 views

### How does the number of function calls in BFGS scale with the dimensionality of space?

Question Is there any estimate for the scaling of the number of function calls in BFGS-optimization with the dimensionality of the search space? Specifically I am assuming a (free) expression for the ...
• 183
1 vote
146 views

### Complexity of solving an image differential linear system

Define an "image differential linear system" as a linear system $A\mathbf{x}=\mathbf{b}$ wherein $\mathbf{x}$ contains the ($\mathbb{R}$) pixels of an image and each row of $A$ constrains ...
• 255
1 vote
236 views

### Asymptotic complexity of fixed-rank SVD

According to the Wikipedia article on Singular Value Decomposition, the asymptotic complexity of computing the SVD of an arbitrary m×n matrix M with m>n by the popular Householder QR methods is O(...
• 131
293 views

### Diagonalization of Hermitian matrices vs Unitary matrices

What are the general algorithms used for diagonalization of large Hermitian matrices and Unitary matrices? ($>5000 \times 5000$) LAPACK seems to diagonalize Hermitian matrices almost 20 times as ...
144 views

### Time complexity of derivation, gradient,differential, jacobian matrix

what is the time complexity of gradient $\nabla_{f}$ using the $\mathcal O$-notation? what is the time complexity of jacobian matrix using the $\mathcal O$-notation? who knows some references to ...
1 vote
49 views

### Most scalable distributed consensus mechanism based on message complexity? [closed]

One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity. For example, PBFT message complexity is O(n^2) that ...
• 111
3k views

### Runtime of Gaussian elimination/row reduction on a rectangular $m \times n$ matrix

The runtime of Gaussian elimination on an $n \times n$ matrix is $O(n^3)$. What is the runtime on an $m \times n$ matrix? I am taking Gaussian elimination to mean putting the matrix in reduced row ...
• 23
60 views

### Which class does this NP problem belong to?

Suppose $n$ inputs ($x_1, x_2, x_3, \cdots, x_n$) can take on any of $m$ values, say $\{ k_1, k_2, k_3, \cdots, k_m \}$, and that there is a cost function $y = f(x_1, x_2, x_3, \cdots, x_n)$. For ...
402 views

### Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices

I just came upon this paper, which details the implementation of a fast method to get eigenvalues of tridiagonal symmetric matrices : Coakley, Ed S.; Rokhlin, Vladimir, A fast divide-and-conquer ...
• 153
1 vote
100 views

### Flops of the computation of symmetric matrix $A$ to the power of $p$

What is the cost in terms of flops for the computation of $A$ to the power of $p$, where $p$ is a positive integer and $A \in \mathbb R^{n\times n}$ is a symmetric matrix?
1 vote
893 views

### Time complexity of numerical finite differences

I have a function $f:\mathbb R^N\to \mathbb R$ and I would like to compute all the partial derivatives of $f$ w.r.t. the $N$ input. What is the computational complexity using the (ones-sided) finite ...
• 21
209 views

### Is there an efficient algorithm for calculation of continued fraction expansion from decimal digits?

Suppose to calculate the continued fraction expansion of $\pi$, the common-sense algorithm would be to take the decimal part, perform inversion, which will give the next term as integer part, and the ...
232 views

### What is an instance (precisely) in computational complexity?

I am trying to understand the notion of reduction of a problem to another problem. As it is known this has huge impact on classifying the complexity of a problem. The definition of reduction involves ...
• 119
189 views

### Big Theta Complexity of Gaussian Elimination using Complete Pivoting

I already know the Big O for partial pivoting is $O(n^3)$ and remain the same for complete pivoting. I also know the big theta complexity for partial pivoting is $2/3 n^3$ I would like to know the ...
• 33
397 views

### Calculate amount of FLOPs for an eigenvalue problem solver

I have 2 complex, non-symmetric, matrices $A_{1000\times1000}$, $B_{1000\times1000}$ and I am using Matlab to get it's eigenvalues (functions like eig or eigs). Both matrices are different - one is ...
• 183
125 views

### Time complexity analysis

I want to know the time complexity of following code Say I have a list unique_element[] There is an array which contain elements {4,5,2,4,7,8,1,5,9,8,1} Now as per my code I want to find out the ...
• 123
21 views

### Cost functions to judge time/memory/accuracy tradeoffs

I am working on an interesting algorithm: Its absolute error is exponential in a parameter $j \in \mathbb{N}$, and for a given $j$, I have complete freedom to choose between an $\mathcal{O}(1)$ time-...
• 2,145
691 views

### Asymptotic Complexity of Gaussian Elimination using Complete Pivoting

I would like to know the algorithm asymptotic complexity with Complete Pivoting. With partial pivoting, it is known to be $O(n^3)$. Is it the same for complete pivoting?
• 23
2k views

• 123
1 vote
299 views

### Generalization error and Sample Complexity estimation for Least Squares

I am wondering how to draw a sample complexity plot similar to the following figure which shows the estimated number of samples to incur no more than 10 percent generalisation error on average for the ...
100 views

### Is the numerical resolution of this huge sparse polynomial system tractable?

I'd like to find numerically a solution to a sparse system of 2000000 polynomial equations of degree 3 with 50000 variables and integer coefficients (or at least to decide whether or not a solution ...
1 vote
99 views

### What is meant by "operations"?

In this paper, on page 243, we have $$d_{jk} = \frac{a_j}{a_k(x_j - x_k)}$$ where $$a_k = \prod_{l = 0;l\neq k}^{N}(x_k-x_l)$$ Now, $a_k$ requires evaluating N multiplications. Why does the author ...
248 views

### Efficient algorithm for a matrix product

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
• 295
115 views

### $LU$ Factorization of a nonsingular matrix with a particular pattern

Consider $S\in\mathbb{R}^{n\times n}$ whose nonzero elements have the following pattern for $n = 8$: \begin{pmatrix} 1 & 0 & 0 & 0 & \mu_1 & 0 & 0 & 0\\ 0 & 1 &...
• 295
185 views

### What kind of optimisation algorithm is suitable for a computationally expensive function?

I have a reference value $R$ and a modelled value $M$. $M$ is generated using a stochastic algorithm with parameters $a$ and $b$. The objective is to tune $a$ and $b$ so that $M$ is as close as $R$ ...
201 views

### Notations for algorithmic complexity in elementary operations

I am comparing several algorithms (moments and matrix products) for real-time computing in terms of numerical complexity in elementary operations. [EDIT] Algorithms are very similar in terms of ...
1 vote
98 views

### Expected runtime complexity of repeated closest Point Pair search

I have to vectors $X_1$ and $X_2$ with 3 dimensional points $p_i$ and $p_j$ contained. As long as $X_1$ is not empty, I want to find the closest pair $p_i$ and $p_j$. The point $p_i$ of this pair I ...
1 vote
What is computational complexity for computing perimeter of a polygon of $n$ vertices? The polygon is not necessarily regular and can be convex or non-convex.