Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computational-complexity]

Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.

3
votes
2answers
20 views

exponential time complexity for $M(n,n)$ with $ M(i,j) = M(i-1,j) + M(i-1,j-1) + M(i,j-1) $.

For $n \in \mathbb{N}$ we define $Q(n) = M(n,n)$ with: $$ M(i,j) = M(i-1,j) + M(i-1,j-1) + M(i,j-1) $$ and $$ M(i,0) := M(0,i) := i \mbox{ } \mbox{ } \forall i \geq 0 $$ Show that $Q(n)$ (regarding ...
5
votes
1answer
45 views

A polynomial algorithm to determine whether a finite group is nilpotent

Does there exist a polynomial (in respect to the order of the group) algorithm that given a Cayley table of a finite group determines, whether a group is nilpotent or not? There do exist polynomial ...
0
votes
1answer
23 views

Complexity of solving a linear equation system over $k[x]$

Let $k$ be a field and let $A \in k[x]^{m \times n}$ be a polynomial matrix whose entry with highest degree has degree $d$. Let $b \in k[x]^m$. What is known about the complexity of computing a ...
2
votes
1answer
47 views

Sum of sqrt of eigenvalues without computing all eigenvalues

Let $A$ be a positive-definite matrix with eigenvalues $e_1, ..., e_n$. I want to compute $\sum\limits_{i=1}^{n} \sqrt{e_i}$ without calculating all eigenvalues first (or rather: with a method faster ...
0
votes
0answers
11 views

ST-CON variation: is it also in NL?

Consider the following variation on the ST-CON decision problem: given a directed graph $G$, for every two different vertices $s$ and $t$, there is a directed path between $s$ and $t$. Intuitively, it ...
1
vote
0answers
17 views

What is the lowest computational complexity of multiplying two non-square matrices?

Based on Wikipedia information, the computational complexity of multiplying two $n\times n$ matrices can be $\mathcal{O}(n^{2.37})$ using algorithms similar to Coppersmith–Winograd. I wonder what if ...
0
votes
0answers
34 views

Derive a bound for a tree with node having k left branches

We are given a binary tree of maximum level n and where each node can have a maximum $k$ left directed edge. $n$ is always greater than or equal to $k$. I want to know a bound on the number of nodes ...
0
votes
0answers
16 views

QR-algorithm complexity on a symmetric tridiagonal matrix

Why does the QR algorithm (for calculating eigenvalues) only require O(m) calculations per step when performed on a symmetric tridiagonal matrix?
2
votes
2answers
45 views

Biased binary search complexity

We know Binary search on a set of n element array performs O(log(n)). We have this recursive equation through which the search space is reduced by half in each iteration, after a single comparison. <...
1
vote
0answers
29 views

Find first eigenvector of Hadamard division of $AA^T$ and $BB^T$ using power method

For an $m \times n$ matrix $A$, it is possible using the power method to find the eigenvector corresponding to the largest eigenvalue of $AA^T$ by factoring it into a matrix vector product $(AA^T)v = ...
0
votes
0answers
11 views

Strassen for Multiplying Three Matrices

Strassen algorithm works for multiplying only two matrices with arbitrary sizes (by using divide and conquer approach). I am wondering if there is an algorithm similar to Strassen but for multiplying ...
0
votes
0answers
13 views

Complexity limitations for randomness

I’m unsure if this is a stupid question, but: In general, is guessing a correct value faster when done randomly, or done incrementally from some basic seed/sequence? For example if I have [1,....,...
0
votes
0answers
3 views

How to show time complexity comparation of Fleury's and Hierholzer's algorithm?

I know that time complexity of Fleury's algorithm equals to $O(e^2)$ and Hierholzer's equals to $O(e)$. I need to show that Fleury's algorithm is less efficient on some example or by giving a proof of ...
0
votes
0answers
78 views

Forward Substitution algorithm. Calculate computational cost.

I have this Forward Substitution pseudocode: ...
0
votes
0answers
12 views

number of multiplications and additions

I would like to count the number of multiplications and addition in Cholesky Decomposition. Assume that I have Hermitian positive definite matrix. First, I will calculate all the entries in the lower ...
1
vote
0answers
26 views

Time complexity of finding neighbors of specific nodes within a threshold in a weighted graph

Let $G$ be a weighted graph and the weights are in the range $[0,1]$. Consider the list $A=[a,b,c,d]$ as a list of nodes we want to find the neighbors of each within a specific threshold $T$. What is ...
-1
votes
1answer
17 views

Time Complexity of finding Diameter of Free Unweighted Graph

What is the time complexity when finding the diameter of an unweighted graph by taking a random vertex, performing BFS to find the furthest vertex U, then perform BFS on that to find vertex V where ...
0
votes
1answer
21 views

how to calculate running time of algorithm for this simple modulus operation?

With "n" being any positive integer, how many times the statement of while loop will be run, related to "n" please? while(n%2 == 0) n=n/2
0
votes
1answer
22 views

Prove the following language is not regular using the Pumping Lemma for Regular Languages

I am trying to use the Pumping Lemma to prove the language $$L=\{a^nb^mc^md^n\}$$ is not regular. However, I am having trouble when selecting the values of x, y, and z to show that xyz is contained ...
0
votes
1answer
20 views

is it possible to convert assignment of a set of boolean variables into a 3cnf propositions in polynomial time?

very interested in knowing if this conversion is possible, i.e if we can create a function that can be computed in a polynomial time is respect to the input size, so that for an input of boolean ...
0
votes
0answers
26 views

Expressing binary length of ternary sequence

I have a problem with expressing binary length of ternary sequence. One of the questions at tutorial sheet from algorithmics specified a question, which can be simplified to a below problem: We have ...
2
votes
1answer
25 views

Is this computational complexity correct?

Let $\mathbf{A}\in\mathbb{R}^{n\times n}$ $\mathbf{B}\in\mathbb{R}^{n\times m}$ $\mathbf{x}\in\mathbb{R}^{m\times 1}$ If cost is being defined in terms of number of elementary opertions then what is ...
0
votes
0answers
18 views

Maximize quasi - dot product

I have to lists of e.g. $10$ integers from certain range let's say $[0,50]$, I want to maximize a value of a sum of multiplication of pairs of values from those lists. I am allowed to multiply two ...
1
vote
1answer
33 views

Determine if a Hamiltonian Cycle exists?

Suppose I have a graph $G=(V, E)$. Removing a subset $R$ of edges from $G$ results in a new graph $G^\prime=(V, E\setminus R)$. The maximum number of edges in $R$ is $|E|$. Suppose I have the graph $G^...
1
vote
3answers
87 views

Iterating over all squarefree composites $\lt L$

I need to iterate over all integers that are: Composite Squarefree Smaller than a limit $L$ And see for each one if it has a certain property (in addition to these 3). Then I need to sum all such ...
2
votes
1answer
52 views

Motivations for Gram Schmidt

I'm having trouble reasoning the motivations for Gram-Schmidt. I understand that it's an algorithm by which one can derive an orthonormal basis that spans the same space when given a set of vectors $\...
0
votes
0answers
13 views

maximise profit with 3 variables given constraint of positivity

i got mixed up in some calculations afterwards i kept messing it up and getting confused. Im trying to maximise profits calculated for surebets. i want to maximise profits or minimalise losses for a ...
2
votes
0answers
21 views

What's the time complexity of character computational algorithms?

I couldn't find any information on the time complexity of the Burnside and Dixon-Schneider algorithms and I was wondering if this is well-known? In his paper, Schneider actually includes a table ...
0
votes
0answers
19 views

How would I work out the worse/best case complexity for this specific algorithm?

So I was given the following algorithm: for (i = 0; i < n; i++) for (j = 0; j < log^2n; j++) print(j) I want to work out the best/worst ...
1
vote
0answers
25 views

Deleting entries in binary matrix to reduce rank

A personal research question led me to the following problem. Suppose a randomly-chosen $n\times n$ matrix over $\mathbb{F}_2$ such that: The main diagonal is all 1's. The weight of each row (i.e. ...
2
votes
2answers
66 views

Big $O$ small $o$ notation True or False

I'm stuck on a few big-$O$ and small $o$ notation True or False questions, any insight would be appreciated. $4n^3+6n+17=O(n^4)$ True. The degree of complexity is directly related to n, but it is not ...
0
votes
0answers
13 views

How can I prove the following question?

For every time constructible function T, if L is in TIME(T(n))(or more specifically D-TIME) class, then there exists an oblivious Turing Machine M that decides L in O(T(n) log T(n)) time.
1
vote
0answers
12 views

Computing number of subsets with bounded sum

Suppose I have a set $\mathcal{S}$ of $N$ positive integers, and I want to compute the number of subsets of $\mathcal{S}$ whose elements sum to at most $M$. Clearly this problem will require ...
2
votes
1answer
45 views

What is the computational complexity of linear programming?

What is the computational complexity of solving a linear program with $m$ constraints in $n$ variables?
2
votes
0answers
22 views

Band matrix $A$ with bandwidth $m$. Count number of operations for LU decomposition.

My definition of band matrix: $A_{ij} = 0$ for $|i-j|>m$. I have to count the number of additions, multiplications and divisions for the LU decomposition without pivoting of a matrix $A$ with ...
1
vote
2answers
85 views

Evaluating the sum $\sum_{i=1}^n i^2\cdot\lfloor{\frac ni}\rfloor$

I need to evaluate the sum $$\sum_{i=1}^n i^2\cdot\lfloor{\frac ni}\rfloor$$ After a little bit of math I found that the above sum is equal to: $$\sum_{i=1}^n i\cdot n - \sum_{i=1}^ni\cdot (n\space ...
1
vote
0answers
27 views

What is the smallest time complexity to solve this optimization problem?

I want to find the best way to solve this optimization problem in the smallest time complexity: Given $$n, C, r_i, p_i,a_i \quad∀ i={1,2,...,n}, $$ $$maximize \quad f(x_1,x_2,...,x_n)=\prod_{i=1}^n {...
0
votes
2answers
28 views

Asymptotic analysis of harmonic series using Calculus

The problem is to proof that Harmonic series $\sum_{i=1}^n \frac{1}{i} = O(ln \space n)$ So, I know that $ln \space n = \int_{1}^n \frac{1}{x} dx$ so, I need to prove that $H(n) = 1+\frac{1}{2}+...+...
2
votes
1answer
55 views

Connecting n keys to n safes in minimal number of attempts

Suppose I have $n$ safes and $n$ keys "arranged in random succession", each safe unlockable by exactly one of those keys. To find out which key belongs to which safe I am allowed to try unlock a safe ...
0
votes
1answer
19 views

How can I choose the highest resulting combination out of arbitrary sized chunks, worth an arbitrary amount each

I am given a set of companies that each want to buy my product in different sized chunks. I have a maximum of 28 Million units to sell and each company pays a different amount of money for their order....
0
votes
0answers
50 views

Can I reverse this notation?

I don't know this is a proper question on this forum but I was reading about computability theory and computational complexity theory and I saw the reduction concept and its notation like this: A ≤p ...
1
vote
1answer
84 views

Finding the Elements from a list which average to a Known Number

I apologize as I am very new to this so my question may not be written very well/formally. What I am trying to do is find which numbers out of a known list would average to a given number. Say the ...
0
votes
1answer
12 views

Algorithm Complexity - Summation - Correctly interpreted how to do it.

I wanted to double check my understanding and working out for a 3 nested for loop algorithm, and working out it's complexity. I've got the right answer, but how I've arrived at it I feel isn't exactly ...
0
votes
0answers
9 views

Why do results shown by diagonalization relativize?

my textbook mentions: "Using an oracle $O$ to show $L \neq B$ then for every oracle $X$ $L^X \neq B^X$. So this fact isnt very intuitive to me. Can someone please help ?
0
votes
0answers
19 views

Stuck in proof for $AM[2] = BP \cdot NP$

I am trying to solve this problem from Arora, Barak Exe 8.3 . For showing $BP \cdot NP \subset AM[2]$ , I have the following Since $BP.NP = \{L | L \leq_R 3SAT\},\ \exists \text{ PTM M st. } \Pr [...
1
vote
0answers
25 views

Query complexity of identifying a subset [duplicate]

Fix an ambient finite set $X$, without loss of generality $X = \{1, \ldots, |X|\}$. You wish to identify some subset $B \subseteq X$ hidden to you. You can gain information about the subset as follows:...
0
votes
0answers
10 views

Runtime Complexity of Recursive Sequence

I am given $T(n)=2T(n-1)+5^n$, and asked to find the runtime complexity. If there were no $5^n$ term, then the $T(n)$ would clearly be linear, $O(n)$. However, does the $5^n$ term make the complexity ...
1
vote
1answer
26 views

Not reachable accept state in DFA

I am trying to show that every deterministic complete finite automaton that recognizes the language $a^*b+b^*$ for $\Sigma = \{a,b\}$ contains a state $q$ such that no accept state can be reached from ...
1
vote
1answer
49 views

Check if an array contains duplicates [closed]

Check if in array contains duplicates in $O(1)$ space complexity and $ O(n)$ time complexity. Examples: ...
0
votes
0answers
16 views

Efficient way to compute the integral $\int_0^{\infty}d\tau f(\tau)\int_0^{\tau}d\theta g(\tau-\theta)h(\theta)$

I would like to know if there exists a way in which the double integral $$\int_0^{\infty}d\tau f(\tau)\int_0^{\tau}d\theta g(\tau-\theta)h(\theta)$$ can be computed (numerically) efficiently. It is ...