# 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,144 questions
Filter by
Sorted by
Tagged with
39 views

### Reference request:Computational complexity theory for GPU

I think that the computational complexity of the addition of Nth-order square matrices is $O(n^2)$ when using a CPU, but it is $O(1)$ when using a sufficiently large GPU. Is there a theory of GPU ...
• 53
1 vote
28 views

### How to programmatically calculate real eigenvalues and (optionally) complex eigenvectors for big matrix

I am trying to solve 1D timeindependent schrodinger equation $$-\frac{\hbar^{2}}{2 m} \frac{\partial^{2} \psi}{\partial x^{2}}+V(x) \psi=E \psi$$ for periodic potential to simulate crystal lattice ...
24 views
+50

• 605
116 views

### References for me to understand current approaches to settle $P$ vs $NP$ [closed]

I am an undergrad student that likes to study approaches to settle $P$ vs $NP$. I know that there is GCT method, and another way is to attack it by logic equivalent. I am a double major student in CS ...
11 views

### What is the time complexity of initialization a static vector and determine functions?

I'd like to determine time complexity of a pseudo algorithm : Where specifying the variables A and B, is giving a value to A and B. Deterring the function E is choosing or writing the function E. ...
• 103
95 views

### Good Algorithm to Compute all Subgroups of a Finite Group.

Let's suppose we have a group $G$ of finite order $n$. We want to algorithmically compute all subgroups, and there are some ways to do that. First one: Compute all subsets. Verify for each of them if ...
• 2,995
15 views

### What is the computational complexity of an equation composed of $2m^2$ divisions and $2m^2$ addition of $2n$ additions?

I want to calculate the computational complexity in term of the big (O). My equation is: Where the $S^+$ and $S^-$ are calculated as follows: Where $\triangle_TOPSIS$ It composed of $2m^2$ divisions ...
• 103
48 views

• 103
4 views

### Clarify answer for asymtotic of median smoothing

Calculating algorithmic complexity for median smoothing in Time Series I came up with the question same as this. Quote it here: A time series with T observations is given. Median smoothing with width ...
• 111
1 vote
44 views

### The rationale behind algorithm for the Modular Exponentiation from the book "Introduction to Algorithms"

I saw this pseudocode from the book Introduction to algorithm (Chapter 31 page 957) on how to implement Modular Exponentiation. ...
• 315
17 views

### (possibly probabilistic) Complexity of recovering a function knowing image

So i ve nearly no knowledge on the subject but i decided to begin a reflexion on AI. And first this is what i discovered, and afer the related problem: Let say you have a set of word of {0;1} of same ...
9 views

### What is the time complexity to finding the least weight for Hamiltonian cycle in complete graph without finding best tour?

As we know finding the best tour in complete graph with n nodes, or the Traveling Salesperson Problem solved by the dynamic programming algorithm in $n^2.2^n$ time ...
• 619
33 views

• 75
28 views

### Maximum flow with minimal number of vertices used

In many of the research problems I encountered recently, the following version of the minimum cost maximum flow problem came up. We are given a directed graph $D$, a source vertex $s$ and a terminal ...
• 43
374 views

### Why is it so difficult to prove $\mathbf{NP} ≠ \mathbf{P}$?

I'm just curious because I saw on Wikipedia a single polynomial time solution to any NP-hard problem would imply there are polynomial time solutions for every single NP problem. Also I assume there ...
• 283
48 views

### Are complexity classes sets?

The definition of a complexity class reads in various different sources roughly as "a collection/set/... of decision problems". My question is: Is every complexity class a set (in the sense ...
• 276
29 views

### Proving NP Completeness of "the project manager's problem"

Suppose we have a list of basic/'atomic' tasks $\{p_1, ..., p_n\}$ and each task has an associated cost $c_i$ for all $i \leq n$. Morover, we have a list of projects $P_1,..., P_m$ which are ...
102 views

### Which grows faster $n!$ or $n^{\sqrt{n}}$?

From graph it can be easily seen that $n!$ grows faster that $n^{\sqrt{n}}$. Also wolfram alpha says that $\lim _{n\to \infty }\left(\frac{n^{\sqrt{n}}}{n!}\right)=0$. I'd appreciate if anyone could ...
22 views

### Evaluate Big O loop worst case and condition statements

Understanding big O, worst case in a loop. Im supposed to count assignation and comparisons, I dont get why? The other doubt I have is if the worst case is seeing/evaluated to infinity or for all the ...
• 33
7 views

### Given a poly(log(G), log(x)) algorithm and N>G, is it also poly(log(N), log(x))?

I have constructed an algorithm that runs in poly(log(G), log(x)). I am now asked to construct one that runs in poly(log(N), log(x)), where N>G. What would make the first algorithm not also run in ...
• 723
1 vote
Fix $d>0$, and let $n$ be a positive integer going to infinity, and for $h>0$, define $E=E(n,h)$ by $$E(n,h) := h\sqrt{\log \frac{1}{h}} + \frac{1}{h}\sqrt{\frac{d\log n}{n}}.$$ A strategy \$h=...