Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit 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.

2
votes
0answers
26 views

Is there a formalised mathematics of sound?

It's an odd question, because sound is so broad. But even more generally I mean to ask is there a mathematical branch which deals specifically with notes, chords, and symphonic complexity in a ...
0
votes
0answers
8 views

Ordering on Time Complexity Classes

In Sipser, the time complexity class $\mathrm{TIME}(f(n))$ with respect to a function $f \colon \mathbb{N} \to \mathbb{N}$ is defined to be the collection of all languages that are decidable by an $O(...
0
votes
0answers
27 views

Compare different optimization techniques.

Usually, the more you know about the function (gradients, Hessians, etc.) and higher order optimization technique is used (Interpolation methods, Quasi-Newton > Newton's method) > the less function ...
0
votes
0answers
6 views

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?
0
votes
1answer
25 views

How to verify that a problem is in co-NP or NP?

In my discrete maths class we dabble a little bit into complexity theory. The lecturer frequently makes remarks such as: " "Is a graph G of n vertices k-connected?" is a problem in co-NP, since if it'...
3
votes
3answers
46 views

Is $O(2^{n/2})$ the same as $O(2^n)$?

Why or why not? It seems like the answer should be no, but on the other hand, it's weird that you'd reach the same value in a constant multiple of n.
1
vote
0answers
26 views

Big Oh Notation: Proving that $n! \in \Omega(7^n)$

Problem I've got the following statement which I'm looking to prove: $\log_2(n!) \in \mathcal{O}(n \cdot \log_3(n))$ The question is: how to do it? Steps taken so far My approach so far was to ...
0
votes
0answers
12 views

Algorithm Complexity

Given an algorithm $\mathcal{A}$ with input parameter $\theta$ with the objective of obtaining $\theta^* = \lim_{k \rightarrow \infty} \mathcal{A}_k(\theta)$. Say we are interested in characterizing ...
0
votes
0answers
19 views

Matrix of a graph and computational complexity

Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ ...
1
vote
0answers
9 views

Complexity of n conjuction in basis {v, ¬}

Please, tell me how to prove that complexity of x1&x2&...&xn in basis {v,¬} = 2n. It is obvious that complexity <= 2n ¬(¬x1v¬x2v...v¬xn), but how to shom that complexity can not be less?...
3
votes
1answer
42 views

Sort an array given the number of inversions

Given an array $A$ with $n$ integers in it, one way of measuring the distance of the array from a sorted array is by counting inversions. A pair of indices $i,j ∈ {0,...,n−1}$ is called an inversion ...
1
vote
1answer
57 views

Fast algorithm to remove edge to get DAG

Given a directed cyclic graph, I want to find if removing a single edge can make the graph a DAG. I came up with a trivial way to do this - remove each edge and check if the graph is cyclic (which ...
3
votes
0answers
37 views

Some questions concerning the generators of cyclic groups

Let $g(p)$ be the least positive primitive root of the prime $p$, the primitive roots being the generators of the cyclic group $\mathbb{Z}_{p-1}$. These are the values for the first prime numbers: $$...
1
vote
1answer
13 views

Optimizing a sum function for computing

For a game project with a leveling system, I have a function which calculates the amount of XP (experience points) to reach the next level, starting from the minimum amount required for the specified ...
1
vote
0answers
21 views

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 ...
0
votes
2answers
43 views

Cost of solving systems of simultaneous linear equations

Given $A,$ a $n \times n $ non-singular matrix and $B,$ a $n \times k$ matrix, I am interested in estimating the computational cost of solving $$AX=B$$ for different values of $k.$ Take as a reference ...
1
vote
1answer
27 views

Time Complexity Of Binary Tree Subtree Algorithm

Given two binary trees, check whether one is a subtree of another one. This is my algorithm. Basically, it says: For two binary trees A and B, A is a subtree of B if they are the same tree. If ...
0
votes
1answer
8 views

How do I find the estimated number of comparisons, using a sorting algorithm on a data set?

just wanted to ask; So if I have a sorting algorithm that performs e.g. n log2 n comparisons And I consider this on a data set of for example; 11,000,000 records/elements How would I find out how ...
0
votes
0answers
8 views

Complexity of maximizing sum of fractional functions under cardinality constraint

Considering the following optimization problem: $max_{x} \ \sum_{i=1}^n \frac{W_i}{D_i - z_i},\quad s.t.\ \sum_{i=1}^n z_i \leq k,z_i\in[0,k]$, where $W_i$ and $D_i$ are postive constants and $z_i$ ...
0
votes
2answers
21 views

How to estimate $n/e^{\sqrt{\log n}}$?

Suppose $f(n)= \frac{n}{e^{\sqrt{\log n}}}.$ So my question is: how can I simplify $f(n).$ Is it possible to write it down like $n^{1-c}$ where is $c$ is a constant?
1
vote
1answer
24 views

Computational Complexity of Euclidean Algorithm for Polynomials

Let us assume that the two polynomials that we have are degree $n$ polynomials. The naive Euclidean Algorithm for univariate polynomial does $O(n)$ divisions and each division takes $O(n^2)$. So ...
0
votes
0answers
20 views

Implication of Mahaney's Theorem

According to this source, Mahaney’s Theorem states that An NP-complete language $L$ is Karp-reducible to a sparse language iff P = NP. The same source states that “…if some NP-complete ...
0
votes
0answers
17 views

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 ?
1
vote
0answers
20 views

The complexity of finding pure Nash equilibrium in exact Potential games

Fabrikant., et al., in the paper "The complexity of pure Nash equilibria" (http://kunaltalwar.org/papers/purenash.pdf) show that finding a pure Nash equilibrium (PNE) in a Congestion game is a PLS-...
1
vote
1answer
46 views

Big-Theta, Big-O, Big-Omega in $\Bbb{R}^n$.

Is the following statement true? Let $ g : \Bbb{R}^n \to \Bbb{R}^n $ $$ \Theta_{(g)} = \Omega_{(g)} \cap O_{(g)} $$
0
votes
1answer
32 views

Given LU decomposition of matrix A, How to solve $(A-uv^T)x=b$?

Homework disclaimer... 9 tasks for homework, out of which 6 required, out of which I can solve 4 but have no idea what to do with the other 2. This is one of these 2. Given the decomposition $PA=LU$...
0
votes
0answers
12 views

Number of empty bins in multinomial distribution

Suppose I have a discrete probability distribution over $N$ bins $\bigl (p_i > 0; \; \sum_{i=1}^N p_i = 1 \bigr)$, and I have drawn $M$ samples from it. Question 1: What is the expected value of ...
-1
votes
2answers
19 views

Proof of worst-case time complexity of Binary Search

I know that using the Master Theorem, one can easily arrive at the worst-case time complexity. However, how would I go about proving that it is in $O(lg(n))$ by defining upper and lower bounds? I have ...
2
votes
0answers
87 views

A combinatorial sum over distinct indices

Suppose I have a symmetric matrix $J \in \mathbb{R}^{n \times n}$, and $p \in \mathbb{N}^*$ (assume $p \ll n$). I want to compute the following quantity: $$\sum_{i_1,\cdots,i_p} J_{i_1 i_2} J_{i_2 i_3}...
0
votes
1answer
31 views

Complexity calculation by using sum notation

I have 3 loops and I've written them using sigma notation. However, I cannot go further. I want to get its result as Big-Oh. Can you help? $$ \sum _{i=1}^{\frac{n}{2}}\:\sum _{j=1}^{\lceil\log n\rceil}...
1
vote
1answer
38 views

How to decide whether a linear subspace over $\mathbb{Z}_2$ is the cycle space of some graph?

Preliminaries: Assume we have a simple graph $G=(V,E)$ (no loops, no multiple edges). If we label the edges with $k=1,\dots,|E|$, its cycle space $C$ can be identified with a linear subspace of $\...
0
votes
0answers
13 views

Find complexity of recurrence relation

I'm trying to find the complexity of this recurrence relation: $$T(1)=1 \\ T(N)=c(\lg N) + T(N/2)$$ My attempt at solution: Let $N=2^k$. Then: $$T(N)=T(2^k)=c \lg(2^k) + T(2^{k-1})=c \lg(2^k)+c \...
1
vote
2answers
32 views

Expressing the upper bound to $f(n) = n * log(n)$ as a polynomial

In order to do a recursive algorithm analysis, I'm applying the master theorem. As part of that, I'm looking to find a value for $\epsilon$ so that $n \log{n} = O(n^{2-\epsilon})$. Now, intuitively, ...
1
vote
1answer
39 views

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?
1
vote
1answer
24 views

Asymptotic Problem Complexity = Infimum of Asymptotic Algorithm Complexities?

When talking about the complexity of algorithms and problems, the complexity of a problem is the infimum of the complexities of the algorithms that solve the problem. My question is: Is the ...
0
votes
1answer
28 views

Prove parity function on n bits has circuit size O(nlogn), using AND, OR, NOT gates.

I was reading a book about computational learning theory, and it said that this should be easily provable. I don't know if it is because of my insufficient background in complexity but I am struggling ...
0
votes
0answers
18 views

Big O in Rademacher

Theorem 2 of these notes states: Let $G$ be a family of functions mapping a set $Z$ to the unit interval $[0,1]$. Suppose that a sample $S$ of size $m$ is drawn according to distribution $D$ on $Z$. ...
0
votes
0answers
63 views

I need an idea to solve this amortized analysis problem

multistack consists of an infinite series of stacks S0,S1,S2, . . . , where the ith stack Si can hold up to $3^i$ elements. The user always pushes and pops elements from the smallest stack S0. ...
0
votes
1answer
18 views

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}$ ...
1
vote
1answer
56 views

Computational complexity of sizes and number of orbits of a group acting on a set

Given a group action of a group $G$ on a set $X$, is there any way to relate the number of orbits, i.e. $|X/G|=|\{\{g\cdot x:g\in G\}:x\in X\}|$, to the sizes of the orbits, i.e. $|\{g\cdot x:g\in G\}|...
0
votes
0answers
39 views

Simplifying $\sum_{i=0}^{\log n} \frac{n}{\log\left(\frac{n}{2^i}\right)}$

$$\sum_{i=0}^{\log n} \frac{n}{\log\left(\frac{n}{2^i}\right)}$$ I'm having trouble seeing how this summation simplifies. It seems it would be something like: $$\frac{n}{\log(n)} + \frac{n}{\log\...
0
votes
1answer
45 views

Groebner Basis calculation for degree 2 polynomials

Gröbner Basis calculation on degree 1 polynomials, namely linear combinations of variables, is the same as Gaussian Elimination, which has a straightforward $O(v^3)$ algorithm: each variable is ...
0
votes
0answers
11 views

Karp hardness of a module in a graph

DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property: For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
0
votes
0answers
37 views

is n! = $\theta((n+1!))$ Asymptotic notation

I had a doubt whether n!=$\theta{(n+1)!}$. In my opinion, it should be correct, as there must surely exist values for $c_1$, $c_2$ such that the definition for asymptotic notation is satisfied. ...
0
votes
0answers
62 views

A Language in CNF with distinct variables per clause and each variable appears in at most three literals is in P

Let A be a language defined thus A = {φ | φ is in CNF, with three literals, comprising distinct variables, per clause; and each variable appears in at most three literals; and φ is satisfiable} . ...
0
votes
1answer
25 views

Optimizing Polygon Search

I split de world in X random polygons. polygons on map Then I am given a coordinate C1, for instance (-21.45, 7.10), and I want to attribute the right polygon to this coordinate. The first solution ...
1
vote
1answer
71 views

Solving an optimization problem with lower computational complexity

Given $$n, C, r_i, p_i, \quad∀ i={1,2,...,n} $$ I want to solve this optimization problem: $$maximize \quad f(x_1,x_2,...,x_n)=\prod_{i=1}^n {{(x_i/r_i)}^{p_i}} $$ $$s.t \quad {(x_i/r_i)≤1}, \quad {(\...
1
vote
1answer
29 views

Simplex Methods and P problems

I know that there are cases in which the simplex methods, in linear programming, needs exponential time to calculate the solution. So why is simplex method considered a P problem ?
2
votes
3answers
54 views

Recurrence Relation when n is a fraction?

If I have the following: $$T(n) = T(n/2) + 3$$ Where $n > 1$ and $T(1) = 2$, how do can I solve for odd $n$ values (e.g. $T(3) = T(3/2) + 3$) ?