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
0
votes
0 answers

Program complexity

We have a two-dimensional $n \times n$ array containing binary values binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel. Enter the number of square areas (with the same number of columns and rows), in of which there are as…
Dzaroslaw
  • 1
0
votes
1 answer

Find a number in unsorted array larger than the median number with complexity better than O(1/2n+1)

Given an unsorted array with N positive integers. Find a number in the array, that is larger than the median number in the array. for example if the array contains numbers between 1-10, the median is 5, so 6+ is acceptable. This can be done with…
Ben Beri
  • 101
0
votes
3 answers

Binary expansions associated with languages

Let $\mathbf{L}$ be the set of all languages over $\Sigma=\{0,1\}$ and $E(\Sigma)$ be a lexicographic enumeration of $\Sigma^*$. Then there exists a bijection from $f:\mathbf{L} \rightarrow [0,1)$ where $f(L)$ has its $i$-th bit (to the right of…
Ganesh
  • 1,721
0
votes
1 answer

Reduction of satisfiability to integer linear programming

Given an instance of SAT, how do I exhibit that instance of SAT into ILP? Do I have to find the satisfying assignment for f first or does this not matter?
C.Lako
  • 51
0
votes
0 answers

What does betweenness mean?

For some reason i could not find a working example on the theory of betweenness.What does betweenness mean when we are talking in terms of ordering problem ?
venom firefox
  • 1
0
votes
1 answer

Nondeterministic Turing machines, tape "forking" and shared memory

I'm describing a nondeterministic Turing machine solving a problem in $NL$-space. Of course I'm making good use of the fact that along with each computational branch, my tape is also "forked". My question is whether it's legal to update a "shared"…
Ilya
  • 273
0
votes
1 answer

A function that is $\mathcal O ( n^{1+\varepsilon}))$

In my study of complexity theory I encountered the following question: give an example of a function that is $\mathcal O ( n^{1+\varepsilon}))$. I have two questions: $(1)$ Would $f(n) = n^{1+1/n}$ suffice? Because if we let $N = \varepsilon^{-1}$…
LSE_Student
  • 209
0
votes
1 answer

The best case of the merge operation in MergeSort Algorithm is lineal

I was doing an exercise of time complexity of the algorithms that I've studied in class and there's something I don't understand. The exercise says: The best case of the merge operation in MergeSort Algorithm is (a) Constant (b) Lineal (c)…
Arnau
  • 341
0
votes
0 answers

Generating all multiplicative partitions of $n$ in time $2^{o(\log n)}$

Is it possible to generate all multiplicative partitions of $n$ in time $2^{o(\log n)}$? $o(\cdot)$ is "small O" notation.
Aurelio
  • 479
0
votes
0 answers

Theory if Computation Problem

Hey I am having a hard time trying to make an implementation of a TM (Turing Machine) that describes a list of n strings over {a,b,c,...,z} of max 2n each have a character common to all. Then on top of that, I have to make a complexity class for the…
Nathan Campbell
  • 9
0
votes
0 answers

Why is $BPP \nsubseteq NP?$

I'm studying for an exam, and one of the practice questions is this: Assume an polynomial probabilistic algorithm exists for an NPC decision problem $A$. For a yes-instance it gives the right answer 80% of the time and for a no-instance 70% of the…
Ivo
  • 101
0
votes
2 answers

Subset sum with multiple lists

Given n lists of m elements each we need to obtain sum S by selecting one element from each list. Is corresponding decision problem NP-complete? Are there papers about it?
DSblizzard
  • 903
0
votes
2 answers

Finding out how many time units will each algorithm spend for sorting an array of $1\,000\,000$ objects

Question: You have found empirically that the implemented sorting methods $A$ of complexity $\Theta(n^3)$ and $B$ of complexity $\Theta(n^2 \log n)$ spent $2$ and $10$ time units, respectively, to sort an array of $100$ objects. Find out how many…
User426190
  • 53
0
votes
1 answer

Big $O$ prove $2n^2 = O(n^2)$ and $2n^2 + n^2m = O(n^2 m)$

I'm stuck trying to prove a Big $O$ notation for two pieces of pseudocode I made. I have analysed each and one comes out as $2n^2$ and the other is $2n^2 + n^2m$. I have to prove the first is $O(n^2)$ and the second is (I believe) $O(n^2m)$ but I've…
Zibbydoo
  • 1
0
votes
1 answer

Why sup is needed for asymptotic notation definition?

I saw in a book that $\ f(n) = O(g(n)) $ iff $\lim_{n\to \infty} \sup \left|\frac{f(n)}{g(n)}\right| <\infty$ my question is: Why sup is needed? The way I understand it, the fraction of two different functions with the same growth rate (for…
joe markovic
  • 21
1 2 3
…
22 23