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
22 views

How to calculate runtime for FOR and WHILE loops? [duplicate]

While there have been many questions/answers around this on stackoverflow and wikipedia, I would like to have a clearer understanding on how to calculate it in layman's terms. I will say that, yes, ...
4
votes
2answers
88 views

Minimum edge deletion partitioning

I'm interested in the time complexity of the following problem: Given a graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{R}$ (so weights can be negative, too), color the vertices in ...
9
votes
2answers
601 views

Why do we say that polynomial time is easy? [duplicate]

For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so. ...
-1
votes
1answer
13 views

Use of Landau notation for determining bounds [duplicate]

Assume that we have $l \leq \frac{u}{v}$ and assume that $u=O(x^2)$ and $v=\Omega(x)$. Can we say that $l=O(x)$? Thank you.
0
votes
0answers
19 views

Why worst case running time of Insertion sort is $\Theta(n^2)$ [duplicate]

From Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Theorem 3.1 For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if ...
7
votes
2answers
62 views

Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?

The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time. $$LIN \subseteq P$$ Since HORN-SAT is solvable in $O(n)$ (as ...
3
votes
1answer
46 views

Devising an Algorithm for Linear Combination with Column Restrictions

Application: We intend to factor an integer $N$ using a variation of the rational sieve. This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ ...
1
vote
1answer
104 views

What is the best complexity of finding a minimum in a matrix?

Given a matrix $\mathsf{a}$ of size $K\times N$, what is the best complexity of finding the minimum value? Here is a pseudo code: ...
0
votes
0answers
42 views

Existence of randomized reduction but no deterministic reduction

What is the consequence to complexity theory of having a randomized reduction from an NP-complete problem to problem $\Pi$ while there is no deterministic reduction from an NP-complete problem to ...
-1
votes
2answers
58 views

Is there a computation that takes the same amount of time to run on any computer? [closed]

I'm looking for research that has been done towards finding types of computations that take the same exact amount of time to run, regardless the amount of computing power one has. I've been thinking ...
1
vote
1answer
42 views

Merging of two convex polygon chains in O(log n)

Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the ...
1
vote
3answers
70 views

minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
5
votes
2answers
93 views

How to compare the time-complexity of an optimized algorithm with that of the original?

I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$). I managed to reduce the ...
0
votes
1answer
18 views

Time complexity of a vertical sweep algorithm with histogram computations

In the paper Quick Detection of Brain Tumors and Edemas: A Bounding Box Method Using Symmetry, Saha et al the authors claim that the running time of the algorithm (Matlab implementation) is ...
3
votes
1answer
25 views

P/Poly class - undecidable lanauge

I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class, a turing machine M accepts language L with advice $ {a_n} $ if: M(x,$ a_|x| ...
3
votes
1answer
34 views

Question as regards a proof of the Time Hierarchy Theorem

I'm referring to the proof outlined here (and wikipedia.org): https://proofwiki.org/wiki/Deterministic_Time_Hierarchy_Theorem In my understanding, if I relaxed the conditions such that $K$ decides ...
2
votes
1answer
32 views

Help Understanding the Type and Complexity of my Programming Task [closed]

I'm working on a programming task that I, without good evidence, have a sneaking suspicion is NP-Complete. With that said, I would like confirmation on this if possible, as well as some suggestion for ...
2
votes
2answers
57 views

Finding a segment which has equal number of segments before and after it

I got this question in a past test that I'm trying to solve but i don't have the solutions to check my self: Given a set of n segments $[a_i ,b_i]$ where $i=1,..,n$ and $a_i < b_i$. write an ...
3
votes
2answers
85 views

Closed form for the recurrence T(n) = T(n-1) + n²

Given the following recurrence: $$ T(n) = T(n-1) + n^2$$ How can I prove it to be $O(n^3)$ with the substitution method? The $O(n^3)$ guess derives from the fact that at every step of the recursion ...
6
votes
0answers
67 views

P vs NP and the Time Hierarchy

Assuming P $\neq$ NP, is it possible that there exists a $k$ such that for all $j$, $\textsf{DTIME}(t^j) \subseteq \textsf{NTIME}(t^k)$? There reason I ask is that I assume P = NP implies that for ...
1
vote
0answers
50 views

Calculating Time Complexity of Quadratic Diophantine Equation

The particular quadratic Diophantine equation: $$ R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY - c = 0 $$ is NP-complete. (a, b, and c are given in their binary representations. a, b, c, ...
1
vote
0answers
23 views

pragmatic way to compute/ search/ match MSBs operation

consider integers represented as base 2 (strings). define a relation called "n-msb matching" that is true when the 1st n msbs (MSB is "most significant bits") match (of two integers). what is a ...
1
vote
1answer
152 views

How to solve T(n) = T(n-1) + n^2?

See title. I'm trying to apply the method from this question: http://stackoverflow.com/questions/13674719/easy-solve-tn-tn-1n-by-iteration-method. What I have so far is this, but I don't know how to ...
1
vote
1answer
50 views

Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete? [closed]

Given a NP-complete problem $A$, with parameter $a$ and a problem $B$ with parameter $b$, such that a problem in $A$ of size $\mathcal{O}(2^a)$ is $\mathcal{O}(b)$ when translated to $B$, is $B$ ...
1
vote
1answer
39 views

Determining most efficient algorithm for a problem [duplicate]

This is a very straightforward question, and I apologize if it is a repeat. All I want to know is if there is any general method for determining how efficient the most efficient algorithm for some ...
1
vote
0answers
21 views

Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here http://www.ams.org/journals/tran/2005-357-08/S0002-9947-05-03610-X/S0002-9947-05-03610-X.pdf ...
3
votes
1answer
64 views

Is the minimal number of colors needed to color a graph some fixed number?

Consider to following decision problem: Input: Undirected graph $G=(V,E)$ Question: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices ...
2
votes
1answer
39 views

Is it possible that low-resource Turing Machines can always “usually” agree with high-resource Turing Machines

Say that a language $L$ is a $f$-approximation of a language $L'$ if, for all input lengths $n$, $L$ and $L'$ agree on at least a fraction $f$ of the inputs. It is known that there are problems in ...
0
votes
0answers
29 views

How to represent an improper binary tree by means of proper binary tree

By definition: a binary tree needs to fulfill 3 requirements: 1) Each node must have at most 2 children. 2) Each node must have a left and right child 3) Left children is written before the right ...
2
votes
1answer
38 views

Probabilistic algorithm with two-sided error

I am currently studying probabilistic algorithms and came across three major complexity classes: BPP: worst-case polynomial time, two-sided error RP: worst-case polynomial time, one-sided error ZPP: ...
5
votes
1answer
48 views

bounded length CoNP proof

Question: Let $A \subseteq $ {0,1}$^* $ be a language which satisfies $|A \cap ${0,1}$^n|=n^3 $ for all $n\ge 10$ Prove that $A \in NP$ implies $A \in coNP$. Thoughts I've been having difficulty ...
0
votes
0answers
38 views

What is the complexity of this recursive merge of two ordered Python lists?

This is not an assignment, but it is related to my Data Structures class. I just wrote this Python code to merge two ordered python lists. I do know that I could do something like this: list1 + ...
2
votes
1answer
26 views

How does one change the probability bounds in probabilistic complexity classes without changing the class?

I see this theorem whose proof is not clear to me : "Let $L \subseteq \{0,1\}^*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \{0,1\}^*$ and $Pr[ ...
4
votes
1answer
179 views

Difference between time complexity and computational complexity [duplicate]

For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most ...
8
votes
2answers
445 views

Difference between time complexity and computational complexity

For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most ...
1
vote
1answer
45 views

Time complexity of linear program? [closed]

I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of ...
4
votes
1answer
135 views

Can we check in polynomial time if the language of a DFA is closed against Kleene star?

I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it.
1
vote
0answers
44 views

Comparison of matrix determinant in less than $O(n^2)$

I was reading this question and I think maybe somebody here could help. This is the idea: Given a matrix $M$ of integers, and a number $d$ is there a way to compare the determinant of $M$ and $d$ in ...
-2
votes
1answer
49 views

Worst case of based on comparison sorting algorithm [duplicate]

Explain by reference to the structure of a decision tree why any sorting algorithm based on comparisons cannot in its worst case use fewer comparison than a number proportional to nlog(n). ...
5
votes
1answer
152 views

Tree decomposition - Fastest algorithm in practise

I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph. I found the paper "A linear time algorithm for finding tree-decompositions of ...
5
votes
0answers
158 views

Time Complexity of a Knapsack-derived problem

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
1
vote
0answers
32 views

How can we reduce a vertex cover problem to shortest acyclic orienatation?

I want to show that shortest acyclic orientation(SAO) is NP complete.Since vertex cover in Np complete so if vertex cover is reduced to shortest acyclic orientation then it will also be NP complete. ...
1
vote
0answers
81 views

Minimum-Maximum recursive algorithm with a non-even partition, complexity [closed]

So I have been trying to find the recurrence relation of the following algorithm in order to compute its complexity. The following algorithm describes how to find the minimum-maximum element in an ...
0
votes
1answer
51 views

Algorithm analysis of nested loop [duplicate]

so I have this code: for (int i=1; i < n; i=i*5) for (j=i; j < n; j++) sum = i+j; And I'm wondering, what's the time complexity of this for ...
2
votes
0answers
33 views

Hardness of a maximum contiguous subarray sum for a sparse multi-dimensional array

Suppose we have a d-dimensional array A (d > 1) where each dimension has length n. The array is given in sparse notation as input, and the number of given non-zero elements is N. We want to find a ...
3
votes
1answer
112 views

What is the worst case running time for an algorithm that combines insertionsort and mergesort?

Suppose that we have an algorithm "combination" that uses insertionsort for $n < 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$? I was ...
3
votes
1answer
45 views

If O(f) = O(g), why also Θ(f) = Θ(g)?

How we can prove that if $O(f(x))=O(g(x))$ then $Θ(f(x))=Θ(g(x))$?
2
votes
1answer
68 views

Weighted closest-pair-of-points problem

I want to solve the following optimisation problem (an approximation or heuristic would be helpful as well). I have two sets of points in the plane: $P=\left\{ p_{1},p_{2},\dots,p_{N}\right\} $ and ...
0
votes
1answer
46 views

Running time of recursive algorithm with geometric series

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
0answers
15 views

Running time of recursive algorithm [duplicate]

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...