Mathematics Stack Exchange
Mathematics 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.

Computational complexity is a part of theoretical computer science that answers questions about how efficient an algorithm is:

  • How much time (as a function of the size of the input) does the algorithm take to produce its output?
  • How much space (such as computer memory) does it require?
  • How much of some other resource does it consume? (For example, this can be the size of a logic circuit solving the problem, or the number of bits of randomness used by a probabilistic algorithm.)

We can similarly ask about the computational complexity of any algorithm that solves a given problem.

Often, very specific details of these answers (such as constant factors or additive terms) depend on specific details such as the computer you're using. To help deal with this, we often stick to determining the asymptotic complexity of an algorithm: see for more details.

A major problem in computational complexity is the P versus NP problem, which asks if a certain class of problems can be solved by an algorithm that runs in a number of steps that's a polynomial function of the input size.

3433 questions
1
vote
0 answers

Computational complexity sum of digits square root

I know that the sum of digits formula is: $\frac{k(k+1)}{2}$ I am calculating the computation complexity of an algorithm whose while loop is increasing at this factor, hence: $\frac{k(k+1)}{2}>n$ At the time when the function increases over $n$, the…
fynx
  • 13
1
vote
1 answer

Because PvNP has yet to be proved does that mean that encryption might not exist?

I'm not well versed enough on the topic of computational-complexity theory but what I think I know is that there is debate over whether or not all problems that can be checked fast can be solved fast. If this is true and all problems can be checked…
Austin Chesnut
  • 11
1
vote
0 answers

Does this count as a one way function?

So I was simply reading up on the P=NP problem and in the article it said that the existence of a one way function would imply that P does not equal to NP. Of course I read up on it since it was interesting and the definition, at least from my…
Horus
  • 295
1
vote
1 answer

Prove or disprove $f(n) = O(f(2n))$

I wonder how to to prove or disprove that $f(n) = O(f(2n))$ I have tried many function, and think it is right, but still don't have any idea how to prove. Could anyone give me a hint about it?
Heisenberg Chang
  • 29
1
vote
1 answer

SAT instance with exponential number of solutions

Given a SAT instance. If one knows that there are exponentially many solutions to that SAT instance, then can one find even one solution in polynomial time?
Turbo
  • 6,221
1
vote
2 answers

Unary Halting Problem

I have some difficulties in understanging what's actually a unary halting problem Few examples of unary languages are following: $A=\{1^k\space |\space k\space is\space even\}$ $B=\{2^k\space |\space k\space is\space prime\}$ In other words unary…
com
  • 5,612
1
vote
1 answer

Is P complexity class closed under union and intersection?

I need to prove if the P complexity class is closed under union and intersection. The problem is that I don't know how to start; What should I use to solve it? Do I need to use Functions in order to demonstrate it?, maybe problems?. And what do…
Alvarillo Fernandez
  • 11
1
vote
2 answers

Time complexity of running a loop where the counter increased by log(j)?

I have the following code snippet and I want to know the time complexity of running it: func fun(int n) { var j = 1, i = 0; while (i < n) { // Some O(1) task i = i + log(j); j++; } } After some calculation, it comes up that the…
shihpeng
  • 113
1
vote
1 answer

Negative linear amortized time cost of operation obtained using the potential function method

For a (linked) list of numbers there are 3 operations available. Insert which operates in a constant time. Inserts a number at the beginning of the list. Remove every second - time complexity is linear. Removes every second number from the…
SlowerPhoton
  • 799
1
vote
1 answer

Which computational complexity is larger, $O(2^n)$ or $O((\log{n})^{\log{n}})$?

Doing algorithm complexity analysis in my assignments, but don't know how to compare these two algorithm complexity, $O(2^n)$ and $O((\log{n})^{\log{n}})$ Which one is larger and why?
Charlie Lam
  • 13
1
vote
0 answers

2sat approximation related problem.

Let $ { L }_{ \varepsilon }$ to be the language of all 2CNF formulas $\varphi $, such that at least $(\frac { 1 }{ 2 } + \varepsilon )$ of $\varphi$ 's clauses can be satisfied. Prove that there exists ${ \varepsilon }' > 0$ s.t. ${ L }_{…
user54061
  • 11
1
vote
0 answers

Counting flops in log function

I am trying to do some complexity analysis counting the flops that the operations when evaluating a function would require, following section 9.7 from the book on Convex optimization by Boyd and Vandenberghe. Particularly, I am looking at the…
urpi
  • 629
1
vote
0 answers

Big Omega Proof Switch

Big omega definition: $f(x)=\Omega(g(x))$ if $f(x) \ge c g(x)$ Is it correct to switch it around to proof: $$g(x) \le c f(x)$$ I am afraid that moving the '$c$' to the other side may change the entire idea. Thanks
user1234440
  • 541
1
vote
1 answer

Polynomial transform (P, NP)

There are problems A and B in NP. Problem A polynomially transforms to problem B. Suppose A is in P. Is it correct to state that this teaches us nothing new about problem B?
Anoonumos
  • 95
1
vote
1 answer

Average Case Complexity Big O notation

In the following function I want to find the complexities. f(n) = nlog(64n!) + n^2√n Use Stirlings Approximation (a) f(n)∈O(n^3 ) True. The upper bound of the function is f(n)=n^(5/2) and it is less than n3. lim f/g = 0; It is also…
Hüseyin Kömürcü
  • 27
1 2 3
…
22 23