Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

0
votes
0answers
30 views

Why $17T(n/16) + n \log n$ satisfies the case 2 of the Master Theorem?

Using the Master Theorem, we have that $17T(n/16) + n \log n$ is $\theta(n^{log_{16}17} log^2 n)$ My question is, why $n \log n = \theta(n^{\log_{16}17} \log^1 n)$, being $\log_{16}17$ approximately ...
0
votes
1answer
96 views

Switching edges and vertices

I am attempting to convert the problem of finding an edge dominating set into a dominating set. I need a way to change the edges of a graph to the vertices and the vertices of a graph to the edges, ...
4
votes
3answers
551 views

Growth rate of $n^{\sin n}$

Is there a way of comparing the growth of functions $ f(n) = n ^ {\sin(n)} $ and $ g(n) = n ^ {1/2} $ in terms of $ O, o, \Omega, \omega, \Theta $ ? Periodically, $ f(n) $ keeps going above and ...
0
votes
2answers
23 views

Lowering the start indexes in sums

I'm implementing a CYK algorithm in my software and I've found a pseudo-code on Wikipedia. Here's its complexity(modified version for special use, which doesn't go from ...
0
votes
0answers
44 views

What is the complexity of computing some problems related to real analysis

I was thinking. I do not know whether my question has any sense. I want to know is there any way to compute analytically or explicitly some of the problems give below. What is the complexity of ...
1
vote
1answer
33 views

problem about computational complexity

Exercise: Prove that the computational complexity of the binomial coefficient \begin{equation*} \binom{m}{n} \end{equation*} is O($m^{2}$$\log^{2}n$). using the fact that the computanional ...
1
vote
0answers
49 views

What makes the permanent lot more difficult than the determinant

The permanent of an $n$-by-$n$ matrix $A$ = $(a_{i,j})$ is defined as: $\operatorname{perm}(A)=\sum\limits_{\sigma\in S_n}\prod\limits_{i=1}^n a_{i,\sigma(i)}$. ...
6
votes
1answer
779 views

Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
3
votes
2answers
195 views

Big O/little o true/false

These are all from Sipser's book, second edition. I was just hoping someone could verify/explain those that are more difficult for me. $2n = O(n)$: true $n^2 = O(n)$: false $n^2 = O(n\log^2 n)$: I ...
3
votes
2answers
30 views

How to figure out the time complexity for an algorithm with dynamic input parameters?

I have an algorithm that depending on the length of the input array and its values could take more or less operations to complete, for example, for a set with some length it could take 10.000 ...
2
votes
1answer
65 views

From programming to mathematics

I'm studying algorithms design and analysis, but there is a code that I can't understand. I know that: Let $\mathcal P$ be the main program, and $\mathcal P \in O\left(\varphi(n)\right)$ with ...
12
votes
1answer
959 views

Minimum number of different clues in a Sudoku

I wonder if there are proper $9\times9$ Sudokus having $7$ or less different clues. I know that $17$ is the minimum number of clues. In most Sudokus there are $1$ to $4$ clues of every number. ...
1
vote
1answer
42 views

Complexity of primenumber test

The german wiki claims that the approach to check if any number before p is a divisor of p is a polynomial time algoritm. I dont understand this claim. Because imho this is linear, which is polynomial ...
0
votes
2answers
37 views

Sum of a sum [algorithm design and analysis]

I'm studying the algorithm analysis of one piece of code, and I have to find the big-O notation of the sum of a sum. ...
0
votes
1answer
55 views

Is there a limit for how “good” a numerical method can be?

Multiplying two matrices $A \cdot B$ of size $n \times n$ in the trivial way requires $n^3$ computations. However, more efficient algorithms such as the Strassen algorithm have a lower complexity of ...
0
votes
1answer
58 views

Understanding the meaning of the Linear speedup

The linear speedup theorem informally says the following thing: If $M$ is a Turing machine that operates with time $f(n)$ to do a certain task on some input $x$ then for every $\epsilon>0$ we can ...
2
votes
3answers
52 views

Help making the distinction between polynomial and exponential time

I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = $\{\langle G,s,t \rangle | G$ is a directed ...
0
votes
1answer
250 views

If the union of two languages is NP-complete, is one of them NP-complete?

Question 1) If $A\cup B$ is NP-complete, and $A$ is NP, and $B$ is P, then is $A$ NP-complete? I don't think so but I am unsure. When I try to reduce $A\cup B$ to $A$, I fail because strings in $B$ ...
0
votes
1answer
32 views

What is the sum of recursive logarithms?

I am trying to deduce the complexity of a rather odd algorithm. I have got it down to this form: $$ O(n \times (\sqrt n)^2 + n \times (\lg \sqrt n)^2 + n \times (\lg \lg \sqrt n)^2 + \space ... + ...
0
votes
0answers
32 views

Why is integer programming in fixed dimension easier than in general?

When the dimension is an a priori fixed constant, then integer programming feasibility (the existence of an integer point in a polyhedron) can be decided in polynomial time. If the dimension is not ...
0
votes
1answer
49 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
0
votes
1answer
46 views

3-SAT vs P/poly

Why is the circuit for a 3-SAT instance not polynomial in size? That is, when I am converting a SAT formula into a circuit, isn't the size of the circuit polynomial, as I have polynomial number of ...
0
votes
1answer
62 views

Find whether $f(n) = O(g(n))$, $f(n) = \Omega(g(n))$ or $f(n) = \Theta(g(n))$ if $f(n) = n^\frac{1+\sin(\frac{n\pi}{2})}{2}$ and $g(n) = \sqrt{n}$.

Find whether $f(n) = O(g(n))$, $f(n) = \Omega(g(n))$ or $f(n) = \Theta(g(n))$ if $f(n) = n^{\big(\displaystyle 1+\sin({n\pi}/{2})\big)/2}$ and $g(n) = \sqrt{n}$. I tried plotting this out - it ...
2
votes
1answer
38 views

Max Word Size as a Function of Number of Words

I want to describe the relationship between largest word length, l, and the number of words in a set, n. Example: For the set ...
0
votes
3answers
77 views

How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number

Given: $$ X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1} $$ $$ z \in \mathbb N $$ Wanted result: $$ Y = \left\{ y_1, y_2, \ldots , y_n ...
2
votes
2answers
508 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
0
votes
1answer
38 views

Natural Decision Problem not in PTIME

Are there any natural decision problems which are guaranteed not to be in $\mathsf{PTIME}$? Preferably natural graph problems like $\mathsf{CLIQUE}, \mathsf{VERTEXCOVER}$ etc. (However, they would be ...
1
vote
2answers
55 views

Proof of a lemma with inequalities

I read a paper about keyword search and just cannot understand the lemma. Please help me to understand it, thanks. Lemma 1: Let $v_1,v_2,\ldots,v_r$ be $r$ non-descending integers in the range from ...
4
votes
1answer
31 views

Is anything nontrivial known about quotients of complexity classes?

This question is just for fun and this is completely outside my area, so it's likely dumb; apologies in advance. By a "quotient" I mean the following: suppose you have two complexity classes, $A ...
0
votes
1answer
20 views

BigOh - How to determine the upper bound dealing with eccentric series?

I would like to know what is the way to determine the upper bound of a series in BigOh terms. For example, suppose the following series is given: 2 + 6 + 10 + 14 + ..... + ((4 * n) - 2) How can I ...
0
votes
1answer
58 views

How to prove $n^2$ is not in $n^3$

How would I go about to prove the simple complexity of $n^2$ is not in O($n^3$)? Also , how would I go about doing this for big Omega and Theta? Ex. Prove $n^4$ is not in Omega(n^3)??
2
votes
1answer
70 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...
1
vote
1answer
181 views

Efficient Verification for Travelling Salesman Problem

Through reading popular mathematical literature, I have learned the following two facts about computational complexity theory: The complexity class NP is the set of problems for which a candidate ...
0
votes
2answers
139 views

The result of O(f(n)) - O(f(n))

My question is in the field of the big-O-notation and complexity/asymptotic functions: Probably something that I'm missing, but I've couldn't find any well explained solution for the following: What ...
0
votes
1answer
87 views

Why can you find a $k$-clique in polynomial time, but determining if there is a $k$-clique is NP-complete?

You can find a $k$-clique in $n^k$ time by examining all possible sets of vertices of size $k$. So why is it NP-complete to determine if there is a clique of size greater than $k$? It looks like you ...
1
vote
2answers
353 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
2
votes
1answer
276 views

What is the difference between the Big O and Big O star (asterisk) operator?

I'm doing some research on algorithms complexity and in different papers I notice both the use of the regular Big-O operator O(...) and a variant ...
1
vote
1answer
63 views

Calculating algorithmic complexity

Given the following bit of code, how would I calculate the complexity? ...
4
votes
1answer
64 views

Complexity of factoring non-squarefree numbers

Consider the two numbers $N_1=p_1\cdot p_2$ and $N_2=p_1^2\cdot p_2$, where $p_1$ and $p_2$ are primes. Is there any factoring algorithm that can factor $N_2$ faster than the asymptotically fastest ...
1
vote
3answers
1k views

Big O notation - Proving that a function is not O(n)

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$. I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$. Many ...
1
vote
1answer
54 views

Odd way to do arithmetic

If I want to divide $9251$ by $29$, the methods taught in elementary school suffice. Now suppose I want the prime factorization of $9251$. The square root of that number is between the consecutive ...
3
votes
3answers
163 views

Why are the hierarchy theorem proofs called diagonalization?

Proofs of the various hierarchy theorems in theoretical computer science (see e.g. http://www.cs.princeton.edu/theory/complexity/diagchap.pdf) are usually called diagonalization proofs. Why they are ...
0
votes
0answers
51 views

How can I find the distribution of a recursive relation with two parameters?

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also ...
5
votes
2answers
523 views

number of strictly increasing sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$?

What is the number of strictly incremental sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$ ? Is there any exact value? How about approximations?
1
vote
0answers
33 views

any approximation for $\sum_{i_3=3}^{n-k+3}\sum_{i_4=i_3+1}^{n-k+4}\sum_{i_5=i_4+1}^{n-k+5}\cdots\sum_{i_k=i_{k-1}+1}^{n} 1, (n \gg k)$?

Is there any approximation for $$\sum\limits_{i_3=3}^{n-k+3}\sum\limits_{i_4=i_3+1}^{n-k+4}\sum\limits_{i_5=i_4+1}^{n-k+5}\cdots\sum\limits_{i_k=i_{k-1}+1}^{n} 1, \quad (n \gg k)$$ ? We know that ...
0
votes
1answer
364 views

What will be the time complexity of insertion if a queue is implemented using two stacks?

A Queue could be implemented using two Stacks. So what will be the time complexity for insertion and deletion in this queue? Thanks in advance.
0
votes
1answer
38 views

Adding a point to shortest path

If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ...
2
votes
3answers
84 views

Determine appropriate $c$ and $x_0$ for Big-O proofs.

"Prove that $f(x)$ is $O(x^2)$:" $$f(x) = \frac{x^4+2x-7}{2x^2-x-1}$$ Let $c=10$ (addition of coefficients of the numerator less the addition of coefficients of the denominator), and $x_0 = 1$ (the ...
1
vote
1answer
69 views

What's wrong with this argument for $NP \ne EXP$?

Let $\{M_i\}$ be any enumeration of all Turing machines in which each machine appears an infinite number of times. Consider the language $D = \{i \, | \, M_i(i) \text{ does not accept within ...
1
vote
1answer
41 views

Correctness of complexity analysis of recursive algorithm

Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?