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

-1
votes
0answers
18 views

How do I prove that 1 function is an upper bound of the other? [duplicate]

If for every $n > 0$ and some $b > 1$, $T(n) \le h(n)$ and $h(n) = O(h(n/b))$ then how can I prove that $T(n) = O(h(n))$, I understand that $T$ is bounded by $h$, so $h$ must be its upper bound, ...
-2
votes
1answer
60 views

What is the algorithm to add 2 binary numbers with boolean operations?

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
0
votes
1answer
46 views

Optimization in multivalued logic. Optimal strings with given patterns

This question comes from an application in multivalued logic. Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the ...
2
votes
3answers
67 views

Could an NP-Hard problem be in P in after a basis transform? [closed]

I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked. So here goes: Take the following problem for example: Let ...
2
votes
3answers
215 views

Analysis of very simple algorithm [duplicate]

I need to find the time complexity of the following simple algorithm. Calculate the time complexity of the following algorithm: ...
0
votes
1answer
58 views

Array search NP completeness

Given an unsorted array of size n, it's obvious that finding whether an element exists in the array takes O(n) time. If we let h = log n then it takes O(2^h) time. Notice that if the array is ...
2
votes
1answer
17 views

Complexity of self-reducible set

I am trying to solve the following problem: A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where ...
0
votes
0answers
30 views

Execution time of function

The following pseudocodes are given. ...
1
vote
0answers
28 views

Parallel time is sequential space

Studying for my qualifying exam, have a past exam here, which has the following question, verbatim: Give a proof of the Folklore statement: "sequential space is parallel time." In other words, ...
0
votes
1answer
24 views

Complexity bound on $RP^{RP}$

This is a homework question, I'm wondering if anyone could help. Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time. The question is given an algorithm in ...
0
votes
1answer
39 views

Time-complexity of recursive defined code [duplicate]

How would I set up a recursive formula for time-complexity for this code: ...
2
votes
1answer
24 views

Can we separate P and E?

Let $\mathsf E$ be deterministic exponential time with linear exponent. Do we know that the inclusion $\mathsf P\subseteq\mathsf E$ is strict? If so, what's the proof? The time hierarchy ...
10
votes
3answers
647 views

Is it really possible to prove lower bounds?

Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use ...
0
votes
0answers
13 views

Creating an algorithm with a certain worse case runtime [duplicate]

The inputs are x sorted lists (in increasing order) and in each list there are j/x elements (we are assured the numbers will work out to be a natural number. eg: j = 9, x = 3 L1 = [1, 2, 5], L2 = ...
0
votes
1answer
35 views

Whats is the meaning of polynomial run-time in input size ? [duplicate]

If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ? Why ? Doesn't the algorithm run in exponential time anyway ? How the input size affects ? ...
-1
votes
1answer
18 views

Scalar by N component vector multiplication faster than O(N)?

Is there a way to multiply scalar by vector faster than just multiplying each element of the vector by that scalar? It feels to me that there should be some exploit to do that. After all we will ...
0
votes
1answer
56 views

Running time of partial algorithms

What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts? Assume, if necessary, that the halting problem ...
2
votes
1answer
43 views

What is the implication of NP-completeness if P=NP?

If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete ...
0
votes
1answer
66 views

Is this problem P or NP?

Given a set of whole numbers $M=\{z_0, ..., z_n\}$ Are there $z_i$ and $z_j$ with $i \neq j$ but $z_i = z_j$? Is this Problem (surely or only probably) in $P$ or in $NP$? Is it $NP-hard$?
0
votes
0answers
10 views

Creating knapsack instance from 2 instances with specific number of solutions

Let 2 instances of knapsack. (items 1...n, with weights $w_1$,$w_2$,.. and some $W_1$, and items 1',2',..m' with $w'_1,w'_2$,.. and $W_2$ size of the container). Suppose now that the first instance ...
-1
votes
1answer
58 views

All optimisation problems have equivalent decision problems

How can we prove the theorem that every optimization problem has an equivalent decision problem, and the optimisation problem is at least as hard as that decision problem? And secondly, I'm not sure ...
1
vote
2answers
31 views

Time complexity for searching $k-th$ element from starting and ending of a linked list

What are the time complexities of finding $8th$ element from beginning and $8th$ element from end in a singly linked list? Let $n$ be the number of nodes in linked list, you may assume that $n > ...
0
votes
3answers
41 views

Complexity of BST [duplicate]

I have the following pseudo-code for printing all nodes of a BST : ...
3
votes
1answer
70 views

Why is the complexity of this nested for loop not $O(n^2)$?

I have the following pseudo-code: mystery(n): if n <= 50 : for i = 1 ... n : for j = 1 ... n : print i*j else : mystery(n-1) For ...
9
votes
2answers
139 views

Efficient algorithm to compute the $n$th Fibonacci number

The $n$th Fibonacci number can be computed in linear time using the following recurrence: ...
2
votes
2answers
41 views

Contradiction between best-case running time of insertion sort and $n\log n$ lower bound?

If the best case for Insertion sort & bubble sort is $O(n)$ then how is lower bound for any comparison sort is $\Omega(n\log n)$? I mean, $O(n)$ is obviously smaller than $\Omega(nlogn)$. What am ...
1
vote
1answer
35 views

IS and matching

I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why. First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a ...
-1
votes
2answers
70 views

What is complexity of checking whether a natural number is a perfect square? [closed]

As the title says, what is complexity of checking whether a natural number is a perfect square?
2
votes
1answer
30 views

Solving recurrence relation

I am trying to find a $\Theta$ bound for the following recurrence equation: $$ T(n,p,k)=T(n,p,k/2)+T(n,p/4,k)+T(n/8,p,k)+npk $$ ...
1
vote
1answer
41 views

Big Omega of 3-Sum Algorithm [duplicate]

An optimized algorithm for the 3-sum problem with an input array N has O(N^2logN) however I read that the Big Omega for this ...
4
votes
3answers
103 views

Termination in infinite-time

Does it make sense to speak of algorithms that take an infinite amount of time to terminate? In particular, suppose we have a loop with a bound function that is initially positive and is decreased ...
1
vote
1answer
45 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
3
votes
0answers
82 views

Are there any algorithms where the recovery of a witness changes the time complexity?

In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but ...
0
votes
2answers
88 views

What is the complexity of recurrence $T(n) = T(n-1) + 1/n$ [duplicate]

What is the complexity of the follwoing recurrence? $$T(n) = T(n-1) + 1/n$$ I highly suspect the answer to be $O(1)$, because your work reduces by $1$ each time, so by the $n$th time it would be ...
10
votes
3answers
998 views

Has the graph isomorphism problem been solved?

Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not ...
1
vote
1answer
39 views

Asymptotic analysis for quicksort on special case

I have the following problem for homework: Given an array of the form $[m+1, m+2,..., n, 1, 2,..., m]$ as an input, analyze quicksort's run time complexity. TIP: check for $m > \frac{n}{2}$ and ...
3
votes
1answer
144 views

Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?

I learned from this post that ${\sf DTIME}^{\text{EXP}}(n^k) \neq \text{EXP}$ for a fixed $k$ for otherwise the Time Hierarchy Theorem would fail in that relativized world. However, is it possible to ...
2
votes
1answer
173 views

Why does the Time Hierarchy Theorem not relativize?

Is it true that $DTIME^A(n^k) = EXP$ for any fixed $k$ and EXPTIME-complete oracle $A$? If not, what do these complexity classes equal and why (because I know that $P^A = EXP$ for any ...
1
vote
3answers
67 views

If A is in P and B is non-trivial, then A ≤p B [duplicate]

On wikipedia's article on Polynomial-time reduction it states: Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input ...
6
votes
2answers
283 views

algorithm time analysis “input size” vs “input elements”

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
2
votes
1answer
61 views

$T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ [duplicate]

I tried to solve the recurrence $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work. How many arrays exist in each step in the recursion tree? Or can I solve ...
1
vote
0answers
35 views

Connection between formula size and time complexity

Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree. Is there a connection between ...
3
votes
1answer
66 views

Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

This is a true/false question: For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k ...
1
vote
0answers
62 views

#SAT Complexity

I have been looking at algorithms for solving #SAT and calculated that simply extending a SAT algorithm like DPLL by adding the negation of a solution to the original formula and solving again takes ...
1
vote
1answer
24 views

Implement opposite() method to tell if there are two opposite numbers, (x,-x)

Let a dictionary with the operations insert(), delete() and search(). Each one of them ...
0
votes
0answers
64 views

Time Complexity of Queue Problem

What is the time complexity of the following problem? Definitions Given a discrete time axis, define a FIFO as a queue unit with the commands: PUSH (data to back of queue), POP (the head of the ...
2
votes
1answer
35 views

Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar ...
9
votes
1answer
343 views

Is there an efficient algorithm for expression equivalence?

e.g. $xy+x+y=x+y(x+1)$ ? The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or ...
2
votes
1answer
87 views

Are there any coP problems

Is there a notion of coP problem? Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?
0
votes
1answer
37 views

Time complexity for two multiplications modulo $p$

The time complexity of computing $MK\bmod P$ is $O((\log n)^2)$. What is the time complexity of computing $MK^2\bmod P$? Is it $O(2(\log n)^2)$ or $O((\log n)^2)$?