the amount of time resources (number of atomic operations or machine steps) required to solve a problem or run an algorithm with respect to the input size.

learn more… | top users | synonyms

0
votes
0answers
6 views

How can I arrive at an asymptotically tight upper bound and prove its correctness? [duplicate]

I am aware of Big-Oh, but often times my bounds are sloppy, which while correct is not tight enough. How can I ensure that my bound is tight? Is there a way to prove or mathematically arrive at an ...
-1
votes
0answers
16 views

What is wrong with the below complexity analysis of Universal Turing Machine's simulation? [on hold]

In Arora Barak at page no. 32 it says that once we perform the shift with $i$ index, the next $2^i - 1$ shifts of that particular tape will have all index less tha $i$. Since in total there can be $T$ ...
0
votes
0answers
18 views

How to calculate order of growth for the given loop? [duplicate]

int sum = 0; for (int i = 0; i < N; i++) for (int j = 1; j <= N*N; j = j*2) sum++; According to me the outer for loop will run O(N), and the ...
2
votes
2answers
85 views

Identifying system events affecting timing behavior of an application

Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job? My question is purely in the context of Worst Case ...
1
vote
1answer
33 views

About showing algorithmic gap instance for the Goemans-Williamson SDP

Using usual notation we have, $SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$ where we mean, $SDP(G)$ = The maximum value that the SDP finds of the objective ...
-1
votes
1answer
32 views

Is the complement of the given language necessarily in NP?

$A$ is a given language so that $A \in NP$. Assume that $P = NP$. Is $A'$ necessarily in NP? What I did: $A \in NP , P=NP$ $P=coP$ (Can be proven by running a TM $M$ as a decider for ...
1
vote
2answers
83 views

Proving that the language of satifiable CNF formulae with primes is NP-complete

Given the following language: $$L=\left\{\langle\phi, n\rangle \ \middle|\ \begin{array}{l}\phi\text{ is a satisfiable Boolean formula}\\ \text{written as POS (in CNF form)}\\ \text{and $n$ ...
4
votes
0answers
39 views

What's the complexity of solving a packing LP?

As we know, we can solve general linear programs in weakly polynomial time and it remains open if it is possible to solve them in strongly polynomial time as well. But what is the situation in the ...
3
votes
0answers
47 views

Upper bound complexity for a tree's particular property

I want to determine if in a given binary tree whose nodes are integers, left subtree's (let's call it L) nodes are multiples of (at least one) right subtree's (R) node(s). I only require ...
5
votes
1answer
64 views

Finding a small element in a changing array

Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like. The array is initialized to zeros. The goal to to support two operations: ...
0
votes
1answer
30 views

Reduction from 4COL to 3COL

I have a problem with following task: $4COL \in PTIME \Rightarrow 3COL \in PTIME$. Is there any elementary proof to do it?
3
votes
1answer
47 views

Proving that if A⊕B ∈ NP then NP = coNP

I got this question: Let $A \oplus B = (A\cap \bar{B})\cup(\bar{A}\cap B)$. Proof that $NP = coNP$ if and only if $A,B\in NP$ and $A \oplus B\in NP$. But I don't know how to proof the ...
1
vote
1answer
57 views

Which types of mathematical functions are the least complex for a computer to compute ?

Let's consider these four function types : Polynomial, Exponential, Logarithmic and Trigonometric. Considering that both input and output values are floating point numbers. How do they rank in ...
3
votes
1answer
51 views

Is matrix “adjoint-squaring” faster than general matrix multiplication?

The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are ...
4
votes
1answer
19 views

How to solve for p in Akra-Bazzi method for analyzing time complexity?

Every single online resource I've looked up on Akra-Bazzi method appears to skip over the same step: They say you have to solve for $p$ without explaining how. If you look up the various PDFs and ...
4
votes
0answers
31 views

What's the time complexity of Monte Carlo Tree Search?

I'm trying to find the time complexity of Monte Carlo Tree Search (MCTS). Googling doesn't help, so I'm trying to see how far I get calculating it myself. It does four steps for ...
-1
votes
2answers
38 views

Graph Isomorphism variant

Question: Given 2 undirected graphs $G_1$, $G_2$, the problem whether exists a subgraph H1 of G1 which is isomorphic to a subgraph $H_2$ of $G_2$. What is the lowest complexity class for this problem: ...
3
votes
1answer
33 views

Complexity of solving LP with a non-linear growth in variables/constraints

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method. To solve a problem which has $k$ variables and ...
10
votes
2answers
228 views

Why not to take the unary representation of numbers in numeric algorithms?

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether ...
8
votes
1answer
141 views

Is there an algorithm for algorithms time/space complexity optimisation?

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of ...
1
vote
0answers
26 views

list of O(n) algorithms [closed]

Where can I find a list of algorithms organized by complexity. I'm curious of what O(n), O(NlogN) algorithms are there. These are the most useful for large datasets. I'm aware of this but it isn't ...
1
vote
2answers
107 views

Context free languages belongs to NTIME(n)?

As the question states, how do we prove that for every L ∈ L2 (context-free class of languages) is true that L ∈ NTIME(n)? Can anyone point me to a proof or outline it here? Thanks!
6
votes
1answer
138 views

Sum of all products of subarrays

For any three-dimensional array $A$ of size $n_1 \times n_2 \times n_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod_{i_1 = 1}^{n_1} \prod_{i_2 = 1}^{n_2} \prod_{i_3 = 1}^{n_3} ...
0
votes
0answers
21 views

Joining k 2-3 trees

I was given the following question, and would like your help with it: Let $T_1, T_2, T_3, ..., T_k$ be a collection of k 2-3 trees. The height of tree $T_i$ is marked $h_i$. Assumptions: 1) every key ...
4
votes
1answer
29 views

How can I calculate optimal batch sizes for calls to an external server?

So I have a large number of commands, say 500,000, that I want to send and run on a server somewhere else, and get the answers back. All of these commands together takes a long time to execute - ...
5
votes
1answer
54 views

Certificates and NP?

My book says a language is in NP if it can polynomially verified if a string belongs to the language with a certificate. It puts no restrictions on what the certificate can be. For instance, for SAT, ...
0
votes
0answers
21 views

Why does not the complement of a language belonging to class NP, also belong to NP in general? [duplicate]

I know that complement of a language belonging to NP, does not necessarily belong to NP. I came across the example $L= \{\langle G,s,t \rangle | G \text{ is a directed graph and there exists a ...
5
votes
4answers
1k views

Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and ...
0
votes
0answers
15 views

Travelling Salesman Variant Lower Bound

The question I was asked (homework) is essentially: - You are given N points in a plane - Prove that any algorithm that connects these points to form a simple polygon (ie. Form exactly one cycle ...
4
votes
0answers
37 views

Complexity class of finding the number of walks of length $k$ that have different vertex sets

Vertex set $A$ is of the form: $A = \{(v_1,r_1),(v_2,r_2),...\}$ where $v_1 \in V$ and $r_1$ refers to the number of times $v_1$ is reached in some walk and $v_j \neq v_i$ whenever $i \neq j$. ...
1
vote
1answer
28 views

Definition of complexity classes?

My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$): $$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an ...
13
votes
2answers
966 views

Why is factoring large integers considered difficult?

I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ ...
0
votes
0answers
15 views

Time complexity with flooring of nested function calls [duplicate]

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as: $function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ ...
2
votes
1answer
46 views

What does it mean when a time complexity has another time complexity within it?

Sometimes, when reading about algorithms or other theoretical topics, I see time complexities that include other time complexities within the expression. For instance, "the best fixed-parameter ...
1
vote
1answer
36 views

Time complexity - least upper bound

I know that Big $O$ notation is used to describe the upper bound of running time of an algorithm, if we consider time complexity of that algorithm. However, I'm not sure why the following is not ...
2
votes
1answer
44 views

Efficient haircuts

I have a real vector $v$. From this vector, I want to extract a sequence of integers, $ix$. The first integer is found by, $ix_0=argmax(v)$. 1 is then subtracted from $v_{ix_0}$, and the process is ...
-2
votes
1answer
65 views

Time Complexity and Optimization for the Algorithm?

I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity. The algorithm is as follows : Label all the vertices ...
4
votes
2answers
339 views

Can the isomorphic graph problem be solved in deterministic polynomial time?

Here is a recent homework problem of mine: Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. ...
3
votes
1answer
43 views

is Co-NP in PSPACE?

Is Co-NP in PSPACE? I think it should obviously be, but I just wanted to make sure. I can find that NP is in PSPACE in Internet, but not on Co-NP.
2
votes
2answers
70 views

O(1) access into an array-like data structure with numerical ranges for keys

Preface: It's been a long time since I've been in school, and my terminology is probably all wrong. Apologies... Summary: I have a data structure with probability ranges assigned to the elements, and ...
3
votes
2answers
69 views

Proof of APSPACE = EXP

I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book. Please give a semi-detailed proof of this. I have found a paper which has this proof(by ...
1
vote
1answer
17 views

Term for an approximation that becomes better as the problem grows

For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and ...
1
vote
1answer
55 views

Sorting array with two elements - in place and minimal number of comparisons, lower bound

Algorithm must be in place. I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ ...
5
votes
3answers
191 views

AND operator of many functions

Suppose we have a set of functions $f_i: \mathbb Z \rightarrow \{0,1\}, i=1, \dots,n $, with the following property: For each $i =1,\dots ,n$, there exists an $x\in \mathbb Z$ such that $f_i(x)=0$ ...
5
votes
1answer
544 views

Can we show that non-determinism adds no power, for some specific running time?

$NP = \cup_{k \in \mathbb{N}} NTIME(n^k)$ $P = \cup_{k \in \mathbb{N}} TIME(n^k)$ Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$? For how large of a $k$ can we show the above ...
-1
votes
1answer
76 views

Running time of amstrong algorithm

I have a problem how to find best, worst, average case in armstrong number algorithm? Here the pseudo-code : ...
5
votes
1answer
93 views

Complexity of union-find with path-compression, without rank

Wikipedia says union by rank without path compression gives an amortized time complexity of $O(\log n)$, and that both union by rank and path compression gives an amortized time complexity of ...
0
votes
0answers
14 views

Evaluate run time and compare these algorithms [duplicate]

Algorithm A divides the problem into 5 sub-problems of half the size. Solving each sub-problem then combining the solutions in linear time. Algorithm B solves problems of size n by dividing them into ...
3
votes
1answer
61 views

State of the art time complexity for getting (tree) descendants by type/attribute

Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only ...
4
votes
1answer
82 views

Counting the solutions to a restricted 0-1 knapsack problem

Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ : Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms. Output: ...