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
1answer
21 views

Space complexity of Bubble sort

I have the following implementation of Bubble sort where it calls a helper method named swap. ...
1
vote
1answer
22 views

What is the Big-O Time Complexity of this code?

I was wondering if someone could please explain what the time complexity is for the code below. I think it would be $O(n)$ because the algorithm will take as much time to execute as there are elements ...
0
votes
1answer
29 views

Array Doubling Size Strategies

I would like to discuss resizing strategies for arrays please. If you have an array of $k$ initial size and it gets full, so you would like to choose from one of the following approaches: Approach 1: ...
0
votes
1answer
12 views

Calculating minimal discriminator of a set of columns in a matrix with unique rows

Having a matrix $M$, with unique rows, how to calculate a minimal subset of colums $D$ such that every row is unique? Also, how to maximize the amount of unique rows, if the number of chosen columns ...
0
votes
1answer
26 views

The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...
0
votes
0answers
20 views

using TRIE for strings?

I saw the following question online: Init - Initlize data structure in O(1). Insert(s) - Add string s to your Data Structure in ...
0
votes
0answers
15 views

Average cost of insertion sort

I am confused how they get $\frac{n^2}{4}$ as average case of Insertion sort. Is it by testing every permutation of input and averaging the same input size then approximating the graph? If so how?
-1
votes
0answers
26 views

A Query regarding Polynomial hierarchy collapse to a finite level [closed]

Assuming a hypothetical scenario that complexity class $PSPACE$ is shown to belong to complexity class $NP^{coNP}$ the Polynomial Hirerchy Collapses to a finite level. Query 1: Which level the above ...
0
votes
1answer
28 views

Efficient random sampling from large discrete distribution

I have a random variable $X$ that can take finite values in $\{X_1, ..., X_n\}$ with probabilities $\{p_1,..., p_n\}$. Is there a computationally efficient way to sample a number from this set? My ...
3
votes
2answers
70 views

Recurrence and Time complexity

I am having problem solving this recurrence. Can anyone help me with this please: $$ T(n) = 2(T(\sqrt n))^2 , T(1) = 4. $$
0
votes
0answers
16 views

Where does this Oracle Problem belong in the Polynomial Hierarchy?

Given a problem $E_0$ such that: Any valid solution $S_0$ if there is any is of polynomial length. Assuming we are able to guess the solution $S_0$, for it to be valid: i. There are a fixed set of ...
3
votes
0answers
61 views

3SAT to 1-in-3SAT reduction with additonal constraints [closed]

The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows: For each 3SAT clause: $x+y+z=1$ Introduce 4 new variables ${a,b,c,d}$ and replace original clause with below 3 clauses: $R(x−,a,...
0
votes
2answers
67 views

How to prove time complexity for this algo?

I have an intuition that this algorithm should have o(n) time complexity but I cannot prove it rigorously. The question is as follows: Suppose you have an n×n 2-dimensional array A such that each row ...
0
votes
1answer
35 views

How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?

The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
0
votes
1answer
69 views

my dsa teacher gave a assignment which is really confusing (i asked my teacher about it but she said just google it and find it out yourself) [closed]

Write best case, worst case and average case time complexity of following categories of algorithm– a. Constant time b. Linear time c. Logarithmic time d. Polynomial time e. Exponential time (this ...
1
vote
2answers
80 views

I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$

I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$. I will omit what I have tried as it has not been useful.
2
votes
1answer
58 views

What is the computational complexity in big O notation of an algorithm computing n^n?

I have a number n of size s. What is the computational complexity in big O notation of an algorithm computing n^n? Let's assume I'm using exponentiation by squaring. The result size doubles when we ...
1
vote
2answers
100 views

is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?

is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$? I can't figure out how to prove or disprove this. if it is true, is it true only when the function $h$ is invertible?
0
votes
1answer
22 views

What's the time complexity of finding all size-$k$ combinations from a set of size $n$?

I'm wondering what's the time complexity of finding all size-$k$ combinations from a set of size $n$(note that $k$ is a known and fixed constant, say $k=3$)? How does it differ from the time ...
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
78 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
39 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
18 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
28 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
21 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
42 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
48 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
52 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
56 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
21 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
34 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
87 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
57 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
17 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
24 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
25 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
47 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
43 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
29 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
53 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
123 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
78 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}\ \...
2
votes
1answer
37 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
41 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
881 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
0answers
17 views

Understand what this phrase is in the Turing

I had a test a few days ago and failed it. There was a question that was not clear to me. This is the question: For the purpose of describing the drawing on the tape of a Turing machine at each step ...
0
votes
2answers
44 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, ...

1
2 3 4 5
42