Questions tagged [complexity]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

Complexity of primal-dual interior-point in terms of "Big O"

How can I get the Big O complexity of a convex continuous problem solved using MOSEK, and includes M continuous variables. I know that MOSEK uses primal-dual interior-point to solve it, but I am not ...
user avatar
0 votes
0 answers
30 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 ...
user avatar
5 votes
1 answer
245 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 ...
user avatar
  • 2,001
0 votes
0 answers
73 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 (...
user avatar
  • 109
4 votes
1 answer
83 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 ...
user avatar
0 votes
1 answer
58 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 ...
user avatar
0 votes
0 answers
51 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 ...
user avatar
5 votes
2 answers
4k 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 ...
user avatar
  • 153
7 votes
1 answer
237 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 ...
user avatar
  • 183
1 vote
1 answer
125 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 ...
user avatar
  • 255
1 vote
1 answer
111 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(...
user avatar
  • 131
2 votes
1 answer
217 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 ...
user avatar
0 votes
0 answers
101 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 ...
user avatar
1 vote
0 answers
40 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 ...
user avatar
2 votes
1 answer
935 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 ...
user avatar
  • 23
0 votes
0 answers
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 ...
user avatar
3 votes
1 answer
214 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 ...
user avatar
  • 153
1 vote
1 answer
89 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?
user avatar
1 vote
1 answer
514 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 ...
user avatar
  • 21
5 votes
1 answer
137 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 ...
user avatar
0 votes
2 answers
126 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 ...
user avatar
  • 119
3 votes
1 answer
133 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 ...
user avatar
2 votes
1 answer
288 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 ...
user avatar
2 votes
2 answers
98 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 ...
user avatar
  • 123
0 votes
0 answers
18 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-...
user avatar
  • 2,001
2 votes
2 answers
462 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?
user avatar
  • 23
3 votes
1 answer
1k views

Computational complexity of Newton's method

the classical Newton's method for non-linear systems of equations is $x_{k+1} =x_k-J_F(x_n)^{-1} F(x_n)$. In pratice, rather than compute the inverse of the Jacobian matrix, one solves the systems $...
user avatar
  • 540
9 votes
2 answers
6k views

Integer operations vs floating point operations

I have been working with an algorithm, which uses additions of floating point vectors, (sparse matrix of floats)x(dense vector of floats) dot products I recently found out that I can get the same ...
user avatar
2 votes
1 answer
192 views

Convergence rate and complexity for convex minimization problem

In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a description of the rate of convergence and corresponding upper bound for the analytical complexity of a minimization ...
user avatar
1 vote
1 answer
720 views

System of ordinary differential equations - time complexity of initial value problem

I am interested in knowing what the time complexity is (in Big-$\mathcal O$ notation) for solving system of $N$ differential equations? I am using ode15s in ...
user avatar
3 votes
1 answer
2k views

Time complexity of $l_2$-norm of a vector

What is the complexity (in flops, floating-point operations) of taking the $l_2$-norm of vector $\mathbf{v}\in\mathbb{R}^n$ (or $\mathbf{v}\in\mathbb{C}^n$ if a difference exists). We have the ...
user avatar
3 votes
1 answer
2k views

Comparing Algorithmic complexity, ODE Solvers (Big O)

I am currently using the following three methods to solve differential equations: 4th order Runge Kutta Method Euler Method Internal scipy methods: ...
user avatar
  • 133
0 votes
1 answer
134 views

finding the growth rate from numerical data

Suppose i have a bunch of 10 data points and i have to conclude whether the increase is $n^2,n^3,\cdots,2^n,3^n, e^n,\cdots$. For example i have the image:- Now the increase is either polynomial or ...
user avatar
2 votes
2 answers
64 views

Efficient Representation of (spatially sparse) spatial time series

Background I have a huge dataset consisting of points (on a plane) together with a timestamp for each point. This is a collection of car GPS measures, giving us the location (latitude/longitude) of ...
user avatar
5 votes
0 answers
464 views

Optimisation of matrix exponential

I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ...
user avatar
  • 51
2 votes
1 answer
165 views

Regarding impractical usage of direct solvers of linear systems [closed]

Since the computational complexity of direct elimilation methods for solving linear systems is $O(n^3)$, it's not practical when the number of dofs is large. But how large would you call it a large ...
user avatar
  • 649
1 vote
1 answer
334 views

Big-O Complexity of Gini Index

What will be the complexity of finding Gini Index of a sorted vector of $N$ values, which is defined as: $Gini(\mathbf{x})=1-2\sum_{k=1}^N \frac{\mathbf{x}(k)}{\Vert\mathbf{x}\Vert_1}(\frac{N-k+.5}{N}...
user avatar
  • 123
1 vote
0 answers
275 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 ...
user avatar
2 votes
0 answers
97 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 ...
user avatar
1 vote
2 answers
97 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 ...
user avatar
6 votes
1 answer
231 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 ...
user avatar
  • 295
0 votes
1 answer
101 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 &...
user avatar
  • 295
2 votes
2 answers
170 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$ ...
user avatar
0 votes
1 answer
195 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 ...
user avatar
1 vote
1 answer
96 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 ...
user avatar
1 vote
0 answers
59 views

I'm using linear programming for production planning. Does the order in which I make products affect the cost?

I have a collection of different scrap aluminium alloys. I want to mix them together to make new alloys with customer-defined compositions. Sometimes this will involve little more than melting down ...
user avatar
  • 11
1 vote
1 answer
100 views

computational complexity for computing perimeter of a polygon

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.
user avatar
2 votes
1 answer
194 views

Probability of reconstructing a word using c substrings from a random sample

Consider a voice recording split into it's phonemes as our sample $S=(s_1,...,s_k) \in \Omega = P^k$. The number of phonemes is $|P| = 40$. Then I have a word $w = (w_1,...,w_n) \in P^n$. I want to ...
user avatar
0 votes
2 answers
246 views

Single Precision a x plus y (SAXPY) terminology

I've been reading books which refers to vector update operations of the form: y := y + ax, where y and x are vector variables and a is a scalar as SAXPY. I understand ax plus y part, but why "single ...
user avatar
15 votes
3 answers
588 views

Scientific Programming Contests

I regularly compete in so called "Programming Contests", where you solve difficult algorithmic problems with your own code and problem solving skills during a limited time-frame. For referential ...
user avatar
  • 253