Skip to main content

Questions tagged [complexity]

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

13 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
0 answers
540 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 ...
ferros's user avatar
  • 51
5 votes
0 answers
2k views

Two-chordless cycle extraction from a failed comparability graph recognition

I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact ...
Gareth A. Lloyd's user avatar
5 votes
1 answer
155 views

complexity constants in median computations same as that of general quantiles?

I would like to know whether the constant in the time complexity of computing the median is different from that of computing general quantiles. In R for example: ...
user189035's user avatar
2 votes
0 answers
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 ...
Sebastien Palcoux's user avatar
2 votes
0 answers
85 views

How to determine the minimum number of multiplication needed for a specific expression?

Is there any algorithm to determine the minimum number of multiplication(division) of a specific expression? and the optimal expression form for implementation? For example, given values of $\cos\...
LCFactorization's user avatar
1 vote
0 answers
305 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 ...
santteegt's user avatar
1 vote
0 answers
66 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 ...
Dave's user avatar
  • 11
0 votes
0 answers
234 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 ...
Israa Ahmed's user avatar
0 votes
0 answers
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 (...
Tan's user avatar
  • 109
0 votes
0 answers
71 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 ...
dexterdev's user avatar
0 votes
0 answers
171 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 ...
X.Q. Li's user avatar
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 ...
Antonio's user avatar
0 votes
0 answers
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-...
user14717's user avatar
  • 2,155