Questions tagged [time-complexity]

The amount of time resources (number of atomic operations or machine steps) required to solve a problem expressed in terms of input size. If your question concerns algorithm analysis, use the [runtime-analysis] tag instead. If your question concerns whether or not a computation will *ever* finish, use the [computability] tag instead. Time-complexity is perhaps the most important sub-topic of complexity theory.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

Do time-constructible functions exist in relativized worlds?

I know that time-constructible functions are necessary to prove the Time Hierarchy Theorem and being computable functions they are computed by Turing Machines. I'm just confused in that since the Time ...
1
vote
1answer
84 views

Is $P=NP$ even if we need infinitely many algorithms?

If $P=NP$ was proven with an algorithm, would that have to mean that there is one algorithm that has to work for all inputs of length $n$? More specifically, what if there were infinitely many ...
1
vote
2answers
41 views

Does $P=NP$ require an algorithm that uses polynomial space?

if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
0
votes
0answers
28 views

What is the complexity of (prime?) factorization with a fixed number of primes?

I was wondering what the complexity of factorization (on quantum computers or classical computers) is if we know that there must be exactly two prime numbers and we know the two prime numbers. For ...
1
vote
1answer
21 views

Query regarding Length of an Input and Time Complexity of algorithms

What is actually meant when we say 'size/length of an input'? As far as I have interpreted it in different books,it means the values of the parameters to be inputted in an algorithm. But I am actually ...
2
votes
1answer
29 views

Is ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$?

I'd like to know if ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$ or not. I know ${\Sigma_2^\textsf{P}}^\textsf{NP}=\Sigma_3^\textsf{P}\subseteq\textsf{PH}$, and I wish to know if this ...
1
vote
1answer
23 views

Complexity of checking graph separation

Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
1
vote
2answers
43 views

Having a set of non unique Key-Value pairs, how can I optimally find a lowest sum subset if distinct keys?

I understand that the title might be confusing so I'll lead with an example. I have the following set (actually a map): ...
2
votes
1answer
125 views

Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
0
votes
3answers
60 views

O(m) time algorithm to check for a strongly connected graph

Given a directed graph G=(V,E) how can I check to see if it is strongly connected i.e. every vertex is reachable from every other vertex. what's a good algorithm to check for this that runs in O(m) ...
0
votes
2answers
60 views

Complexity analysis for finding all powers of 2 within a range

Suppose you're given $x,y$ integers s.t. $x \leq y$. I want to find all values $\in [x, y]$ (inclusive) that are a power of $2$. There's a $O(\log y)$ approach, where you just start at $1$, and ...
1
vote
0answers
32 views

How does Bowyer-Watson algorithm for Delaunay triangulation run in $O(n^2)$ but runs over all the simplexes?

The Bowyer-Watson algorithm for Delaunay triangulation is known to run in $O(n^2)$ according to the authors, where $n$ is the number of data points in $\mathbb R^d$. In addition, the algorithm (for ...
1
vote
0answers
35 views

Sequence of points on a line whose intervals represent a set of contiguous integers

If I have points on a line at positions (0), (1), (3), and (7) the set of intervals between any two points is the set of integers (1,2,3,4,6,7). In-general, a set of N unique integers can be ...
2
votes
0answers
89 views

Why there is $\log n$ factor in time constructible definition?

I saw two different definitions of time constructible functions. In Sipser (third edt), Definition 9.8, defines $t(n)$ is time constructible if $t(n)\geq O(n \log n)$ and maps $1^n$ to the binary ...
0
votes
2answers
122 views

Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
0
votes
0answers
18 views

Selecting five binary vectors that when multiplied elementwise are most similar to another vector

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
0
votes
0answers
25 views

Polynomial time function vs polynomial time algorithm

In the book Proof Complexity By Jan Krajicek, the definition of a functional propositional proof system is given as: Definition 1: A functional propositional proof system is any polynomial time ...
0
votes
1answer
30 views

Recursive Prefix-Sums K times

I have been wondering about the following question for quite some time: You are given an array $x$. Define f(x) as the prefix sums of this array. For example, f([1,0,1]) = [1,1,2] and f(f([1,0,1])) = [...
0
votes
0answers
52 views

Merging the submatrices' time complexity in matrix multiplication

This is a problem of CLRS: What is the largest $k$ such that if you can multiply $3 \times 3$ matrices using $k$ multiplications (not assuming commutativity of multiplication), then you can multiply $...
0
votes
0answers
14 views

Algorithm speed-up assuming other cnditions unchanged

An algorithm uses $f(n)$ operations. Another algorithm for that purpose, uses $f(n)-g(n)$ operations. I want to calculate the speed-up percentage: Which is $\frac{second\ speed-first\ speed}{first\ ...
1
vote
1answer
72 views

Complexity of LTL realizability of safety games with Next operator only

It is known that the computational complexity of deciding whether an LTL specification is realizable in a safety game is 2EXP-complete (that is, you receive an LTL formula, where some variables belong ...
0
votes
0answers
30 views

Logarithmic space and time computable function for sequences over $\{0,1\}$

Given $\sigma_1 \dots \sigma_n$ a sequence or word of length $n$ over $\{0,1\}$ I was wondering if there is a computable function to calculate $\sigma_m$ in $\log(P(n))$ time where $P(n)$ is some ...
0
votes
1answer
61 views

Lower bound on worst-case time complexity of all sorting algorithms neglecting reading input and accessing elements time

We know that the worst-case time complexity of any comparison sorting algorithm is $\Omega(n\log n)$. Is there a lower bound on the worst-case running time of sorting algorithms of any type? Not just ...
1
vote
2answers
125 views

Need the type of time complexity and its formula

If the complexity of my problem is $O(f_n(n))$ begins at $n =4$ and increases in this sequence: At $n = 4$ the number of operations = $(n - 2)$, $n = 5$ the number of operations = $((n - 2) (n-2)(n-...
-4
votes
3answers
90 views

What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more: Suppose ...
0
votes
1answer
42 views

Proving upper/lower bound

$f (n) = Θ(f (n/2))$ The counter example in the solutions was $f(n)=\sqrt{n}$. But then we get for every $n\ge n_{0}$ $\sqrt{n}\le c_{0}\sqrt{\frac{n}{2}}\ \ ->\ \ n\le c_{0}^{2}\cdot\frac{n}{2}\ \...
0
votes
1answer
39 views

Reduction from language in P to another language in NP

I have a question I was unable to do, from a last test I had. This is the question: Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
0
votes
1answer
54 views

Time Complexity - Palindrome Partition

I am solving an interview practice question: Partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. My solution is as below, and was ...
5
votes
5answers
888 views

Prove a lower bound

Prove: $n^{5}-3n^{4}+\log\left(n^{10}\right)∈\ Ω\left(n^{5}\right)$. I always get stuck in these types of questions, where there is a $"-(xy^{z})"$ in the expression. Whenever I see the solutions for ...
0
votes
2answers
111 views

Complexity of `n & (n - 1)` should be O(1) or O(log n)?

I'm looking at the methods posted in https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ for checking whether n is a power of 2. Method 5, ...
0
votes
1answer
30 views

How to know if language is in comp or np?

I'm new to the site. I had a test a few days ago and failed it, I had a question I did not understand. This is the question: Let's look at the FALSE language: Collect all the verses P in the form of ...
0
votes
1answer
52 views

What is the complexity of computing $C(n + m, m)$?

$C$ here represents combinations. $$ C(n + m, m) = \frac{(n + m)!}{n! m!} = \frac{(n + m) * (n + m - 1) * \ldots * (n + 1)}{m!} $$ In this formula it looks like it's $O(m)$ because both the numerator ...
1
vote
2answers
79 views

"Polynomial Counter" Turing Machine

I need some help with this question: Definition: A Turing-machine that is a counter for the language $L$ is called 'polynomial counter' if there exists a polynomial $p$ s.t. every word $w\in L$ ...
1
vote
1answer
22 views

Complexity of binary search on contiguous, nonoverlapping segments of an array

Suppose that we have an $n$ sized array that it broken into $m$ contiguous, non-overlapping chunks such that when the chunks are concatenated, they form the original array. Say we perform a binary ...
2
votes
2answers
654 views

Betweenness Problem for Binary Comparisons is NP-Complete

I have a very simple question and wanted to check whether my answer is correct. Suppose we are given a list of comparisons $x_1>x_2,..,x_k>x_i$ then consider the decision problem asks whether ...
0
votes
0answers
33 views

Which is better $n^3\log n$ or $n^3$ [duplicate]

I am confused between $n^3\log n$ and $n^3$. Normally $n\log n$ is better than $n^3$ but what's about $n^3\log n$
1
vote
1answer
77 views

Faster algorithm for specific inversion count (part 2)

Following the issue from Faster algorithm for a specific inversion: We have a permutation (a derangement actually) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$. I want to compute ...
3
votes
1answer
540 views

Faster algorithm for a specific inversion

There is a permutation (more precisely a derangement) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$. I want to compute the following counts (a kind of inversion): $$K(\sigma )_{i}=\#\{j&...
1
vote
1answer
24 views

Given a list of comparisons, sort items with as few additional comparisons as possible

You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons ...
0
votes
2answers
28 views

Sorting from independently chosen comparisons

I want to sort a list of n items from pairwise comparisons. Each round, I receive k comparisons, one each from ...
0
votes
0answers
19 views

Time Complexity of given functions [duplicate]

What is if we have f(n) = 15n^2logn +500n^2,5 , g(n) = n^3 + 1000 , h(n) = 21n^3logn , x(n) = 50n^2,5 + n*log(n) How to check " is ...
0
votes
1answer
43 views

Ask for help to prove a inequality, thanks

Can anyone help to prove that $\sum\limits_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) > cn$ for some constant $c>0$? Here $k=\Big[\frac{n}{2\log_2 n}\Big]$ and $[x]$ denotes the integer ...
0
votes
1answer
54 views

Writing efficient code [closed]

I am new to programming and trying to get better at writing efficient code. The obvious thing to do is practice and gain experience. I did learn a few general pointers through exercising, but in most ...
0
votes
1answer
71 views

Can this recursive algorithm be converted to an iterative algorithm in O(1) space?

I am trying to convert this recursive algorithm ...
1
vote
3answers
139 views

Spanning tree whose sum of edge weights are between two boundries

I saw this problem: $\langle G,w,k_1,k_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k_2$ and greater than $k_1$. The problem says that we can prove this ...
1
vote
1answer
22 views

NP problem: certificate concept clarification

When proving a problem in NP, e.g. k-clique problem defined as k-clique:= {<G,k>| G has a clique of size at least k }, from what I understand is that all we assume for the certificate "c&...
0
votes
1answer
39 views

Best algorithm for Decisional 4-XOR problem?

Decisional 4-XOR Problem: Assume $M>>n$ (e.g. $M=50n$ ). Let $A_1,A_2,A_3,A_4$ be sets consisting of $M$-bit elements. Each set has order exactly $2^n$. Decide whether or not there exists $a_i \...
-1
votes
1answer
52 views

Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
1
vote
2answers
287 views

Understanding Time Complexity

I am sorry if these are such stupid noob questions. I am just getting into CS. I read a passage in a book that says: Time complexity is written T(n). It gives the number of operations the algorithm ...

1 2
3
4 5
44