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

How to pronounce the complexity of an algorithm

I have a few questions regarding complexity: How do you name this complexity: $ f(M,D) = O(M^D) $. Is it f is exponential in D and what exactly in M, polynomial? Just to confirm $ f(M,D) = O(MD)$ is linear in both M and D, right? Also is $f(M,D) =…
Marco Goretti
  • 1
0
votes
1 answer

Time complexity comparison between two functions

I'm confused as to how $f(n)$ can be $O(g(n))$, $\Theta (g(n))$ and $\Omega(g(n))$. Could someone help explain?
user201668
  • 3
-1
votes
1 answer

runtime complexity

i want to Order these runtime complexitys ascending. I tried to transform this and made a first try in ordering them which you can find behind the --> $log4711$ --> 1. $log^4(n)$ --> 2. $log(n^4)$ --> $4log(n)$ --> 3. $\sqrt[4]{n}$ -->…
Dirk Vorgerb
  • 1
-1
votes
1 answer

time complexity and big O notation of sub set dynamic programming

given set of $n$ positive integers and a target number $T$ there is an dynamic programming algorithm that run in $O(n T)$ time complexity that solves the sub-set sum problem, It is regarded as exponential in terms of $T$, when $T$ is a big number,…
Ahmad
  • 1,380
  • 1
  • 18
  • 37
-1
votes
2 answers

How can I calculate the computational complexity of an equation composed of $2n$ multiplications and $2nm^2$ additions?

I want to calculate the computational complexity in term of the big ($\cal O$). My equation is: It composed of 2n multiplications and $2nm^2$ additions. The complexity of this equation is it ${\cal O}(2n + 2nm^2)$ or ${\cal O}(2n \cdot 2nm^2)$?
stevGates
  • 107
-1
votes
1 answer

Prove that $(\log(n))^{100} = O(n^{0.01})$

I am really having difficulty getting started with this. Please help me prove that $$(\log(n))^{100} = O(n^{0.01})$$ (Should we use induction for this?)
Hidden Dragon
  • 13
  • 3
-1
votes
1 answer

I have to prove this inequality using the complexity classes.

I know that little-o is < or = to big-O. Θ(n log n) ∪ o(n log n) = O(n log n)
Julian
  • 11
-1
votes
1 answer

algorithmic complexity of "smallest power of 2 greater than n"

If an algorithm will take as long as some constant times the smallest power of 2 greater than $n$, is it $O(n)$? In favour: $2^{\log_2n + 1}$ would seem to imply $O(n)$ Against: There is no $c$ where the algorithm always takes less than $cn$…
Omroth
  • 99
-1
votes
2 answers

Prove that $O(3^{2n}) \subseteq O(2^{3n})$

I need to prove that $O(3^{2n}) \subseteq O(2^{3n})$. So far I have made this solution: I)Lets assume that this is true, and that there $ \exists \space c \in \mathbb{R}^+ $ such as $$3^{2n} \leq 2^{3n} * c$$ II) therefore this fraction must be…
nocturne
  • 83
-1
votes
2 answers

What do the phrases "decision problem" and "complexity class" really mean?

If I understand correctly, the phrase "decision problem" basically means a subset of $\mathbb{N}$. A complexity class is a set of decision problems, ergo it's a set of subsets of $\mathbb{N}$. A decision problem $D$ is in a complexity class…
goblin GONE
  • 67,744
-1
votes
1 answer

Reductions from language to language in $L$ and polynomial time.

For language $M ⊆ \{0, 1\}^*$ lets denote $And(M) = \#(M\#)^*$ and $Or(M)=\#\{0,1,\#\}^*\#M\#\{0,1,\#\}^*\#$. We can say that language has $AND$ ($OR$) property with respect to polynomial reductions if there exists polynomial reduction from…
Haskell Fun
  • 113
-1
votes
2 answers

Proving whether $1.117 * n^2 * \sqrt{n} \in O(\log \log n)$ is valid

For starters both functions, $1.117 * n^2 * \sqrt{n}$ and $\log \log n$ for $n > 0$, increase monotonically with $n$.
four_lines
  • 638
-1
votes
1 answer

P vs NP, finding algorithms in polynomial time?

Concerning an NP problem, such as the travelling salesmen problem. Say for a graph with N nodes there exists an algorithm $A(N)$ which can solve the problem in time $N^3$ (for example). But.... to find each algorithm $A(N)$ takes $2^N$ steps.…
zooby
  • 4,343
-2
votes
1 answer

Blum's axioms and the space complexity measure

I'm asked to prove that the measure $\Gamma_e(x) = s ~ ~ \iff ~ ~ \varphi_e(x)$ uses exactly $s$ work tape cells (i.e. once it halts, the number of tape cells used by a Turing machine to compute it is equal to $s$) is a complexity measure wrt Blum's…
Thomas
  • 932
-2
votes
0 answers

How to simplify Big $O$ notation?

Here are my questions: Simplify the following $O$-notation statements as much as possible, e.g. $O(n + 25 + \log(2n)) = O(n)$. (i) $O(n^2 + n)$ (ii) $O(\log(2n)) + O(n) + O(n^2)$ (iii) $O(n) * O(\log(2n)) $ (iv) $O(2^n) * O(n^2 + 2^n + \log(2n))$ I…
Dan Stephens
  • 1
1 2 3
…
22
23