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

Worst Case for AVL Tree Balancing after Deletion

After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST). The Balancing ...
0
votes
1answer
18 views

Complexity of generating power sets

Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a ...
0
votes
1answer
39 views

how to reduce the time complexity?

I have a graph G=(V+E) and list of list Node where each sublist is subset of V. I want to ...
0
votes
2answers
25 views

Time Complexity of inserting a vector to a vector of vectors in C++

I was solving a question on LeetCode, where I had to generate all possible subsets of a given set of numbers. Although, the solution makes sense to me, I am unable to understand the derivation of time ...
0
votes
0answers
15 views

Time complexity - Head stay transition - Turing Machine

I'm checking time complexity in a turing machine. There is a transition that doesn't move the head, it justs stays (not right nor left movement) . Should I count that state transition to calculate the ...
1
vote
0answers
52 views

Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?

I have a set $M$, subsets $L_1,...,L_m$ and natural numbers $k,l\leq m$. The problem is: Are there $l$ unique indices $1\leq i_1,...,i_l\leq m$, such that $\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}...
0
votes
1answer
28 views

Complexity analysis of m!/n!(m-n)!

Given the runtime of an algorithm to be m!/(n!*(m-n)!) That is mCn, where both m and n are variables, is the complexity factorial or polynomial? Or is it something else? Please elaborate. Thanks
3
votes
0answers
54 views

Maximize area of light with 4 light sources on a diagram of a room

Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized. Here is a simple ...
0
votes
1answer
45 views

Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

We know that the number of permutations possible for $n$ unique items is $n!$. We can uniquely label each permutation with a number from $0$ to $(n!-1)$. Suppose if $n=4$, the possible permutations ...
-2
votes
0answers
27 views

Solving subset-sum encryption (Princeton Creative Assignment)

The question: https://www.cs.princeton.edu/courses/archive/spring03/cs226/assignments/password.html Input files: ftp://ftp.cs.princeton.edu/pub/cs226/password/ The question asks to use a symbol table ...
2
votes
1answer
34 views

How do you find all integers in a sorted array of size n that appear n/k times?

I try to find the solution to this problem: How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time? I could only find this question, where O(klogn) ...
9
votes
7answers
4k views

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$. def is_equal(a: int, b: int) -> bool: return a == b <...
-1
votes
0answers
29 views

Runtime Complexity of finding a loop in an array

Having a hard time understanding the runtime complexity of the following algorithm: ...
0
votes
2answers
31 views

What is the time complexity of sorting n words length wise and then alphabetically? Should we consider the length of the strings in the complexity?

Let's assume I have a list of some words found in the English dictionary: ["hat", "assume", "prepare", "cat", "ball", "brave", "help&...
2
votes
1answer
66 views

What is the expected time complexity of checking equality of two arbitrary strings?

The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters. So far so good. I think we can all agree that ...
2
votes
0answers
22 views

Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph

As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
0
votes
1answer
30 views

Estimating the bit operations using big O notation

Using big- O notation estimate in terms of a simple function of $ n $ the number of bit operations required to compute $3^n$ in binary. I need some help with the above question. The number of bit ...
-1
votes
0answers
13 views

Computaional Complexity of Frobenius Norm

How can I calculate the computaional complexity of Frobenius norm of each column vector(M X 1) in a M X N matrix and finally sorting the norm values in descending order? To clarify I have N-column ...
0
votes
1answer
20 views

Do we have to calculate time for declaring statement in RAM model?

Do we have to calculate time for declaring statement, in my case int num3 statement. The following question was asked by professor as a post-lecture quiz. I ...
-1
votes
1answer
39 views

turing machine accepting language {ww} has ω($n^2$)

prove or disprove that any turing machine which accepts language $l=\{ww | w ∈ \{0, 1\}∗ \}$ has time complexity $ω(n^2)$
0
votes
1answer
46 views

Is finding solution to a system of 2SAT equations seperated by OR (DNF form) in NP

I want to know if finding solution to a specific number of 2SAT equations sepearted by OR gate (DNF form as below) is in P or NP. The equation has total n variables and each clause is a 2SAT equation ...
0
votes
1answer
23 views

Splitting a group of numbers into $k$ sorted groups

I have this first task: You have a set of numbers $S =\{ \dots \}$ of length $n$. And a number $k$. Both $n$ and $k$ are powers of $2$ and: $1 < k < n$ Your task is to write an algorithm (...
-5
votes
0answers
24 views

number of constraints and variables

i have the following formulation and I want to know the number of variables and constraints
1
vote
1answer
33 views

Complexity of class finding selection of entries in matrix

Suppose I have a matrix with entries either $x$ or $y$, where the number of rows = number of columns = $n$. If I want to select/circle $n$ entries such that for each row, only exactly one is circled, ...
2
votes
1answer
23 views

Why minimum vertex cover problem is in NP

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23): Is the size of the minimum vertex cover in $G$ at most $k$? ...
2
votes
1answer
28 views

Euclidean geometry theorem proving complexity

Euclidean geometry is complete, so the problem of determining whether a statement $A$ is provable is computable. Do we know its time complexity?
0
votes
1answer
23 views

How to estimate the complexity of sequential algorithm given that we know the complexity of each step?

First case: I was stumble upon a two step sequential algorithm where the big O complexity of each step is $O(N^9)$. Second case: Also if the algorithm have three steps where the complexity of step 1 ...
2
votes
1answer
64 views

Complexity of Integer Factorization

In Quantum Information and Quantum Computation by Nielsen and Chuang, they define the complexity class NP as follows (page 142): A language $L$ is in NP if there is a turing machine $M$ with the ...
1
vote
1answer
62 views

Complexity of enumeration vs complexity of counting

I have a problem understanding the difference between complexity of enumeration and counting. We can solve every counting problem using enumeration algorithm. Now, I have problem with the following. ...
0
votes
1answer
8 views

Why is the hitting set problem in NP

I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979): INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$. QUESTION: Does $S$ contains a ...
0
votes
0answers
28 views

Looking for fast LP solver algorithm for my Special case

I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly ...
1
vote
2answers
59 views

How to determine if given “complex” time complexity is $O(n^2)$?

If a given time complexity, such as these: $(n + \log n) * \sqrt{n+\log n}$ $n * (200 + \log^2 n)$ $(7+n^3)\log(n^5)$ is not determinable by just looking at it whether is it in class $O(n^2)$ or not,...
0
votes
3answers
97 views

Big O vs Big $\Theta$ during coding interview

Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$. From the book "Cracking the coding interview": "...
0
votes
1answer
38 views

What is the time complexity of subset testing?

Consider the following problem: Let $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_m\}$ be two finite sets over $\mathbb{N}$. The sequences $a_1,...,a_n$ and $b_1,...,b_m$ do not have to be sorted. ...
1
vote
1answer
33 views

How to solve recurrence

I have tried solving it using substitution. Apparently, it is exact for some $n$ and the order of the general solution can be found from this exact solution. By substitution I got the following (not ...
0
votes
1answer
22 views

How to find the square with the highest total sum

I have an integer matrix of size 4n x 4n. I need to select a part of the matrix of size n^2 from which adds up to the most. For ...
0
votes
1answer
11 views

one for loop wraps 2 indexof method, what is the time efficiency?

I'm confused about how to know the time / space efficiency. If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(...
0
votes
0answers
21 views

Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems? [duplicate]

Assuming the Exponential time hypothesis is true, what's the fast possible algorithm that can be produced for NP-complete problems? If 3-Sat takes exponential time, then could it be possible that ...
0
votes
0answers
18 views

What decision problems are their that are outside of elementary but still decidable

What decision problems are their that are outside of ELEMENTARY but still decidable? I'm curious about problems that are still solveable, but take a very long time to do so.
0
votes
0answers
16 views

Given L1 and L2 in NP, if L1 transforms L2 and L2 transforms HC then L1 NP complete?

Why this Question is False ? NP-complete problems are the hardest problems in NP. if L is in NP-complete then [L must be in NP, all problems in NP can be transformed to L]. Does this mean that L2 ...
1
vote
1answer
25 views

Quicksort Time Complexity

I am learning the Quicksort algorithm and I am struggling with understanding the time complexity. Here is the JavaScript ES6 code for the partition function that is used in the algorithm: ...
0
votes
1answer
33 views

What's the complexity class of determing the halting problem of a finite memory Turing machine?

What's the complexity class of determining the halting problem of a finite memory Turing machine? What is the computational complexity class of determining whether a machine halts on any input if it ...
0
votes
1answer
24 views

Space and time complexy of operations on 32-bit array vs. binary array

Assume an array a of length $n$. I am wondering how to characterize the difference between time- and space complexity of 32-bit arrays of length $n$ and bit-arrays of length $n$. Normally, you'd just ...
3
votes
3answers
517 views

Given A to C, and B to C with known complexities, what can be said about A to B?

Say I have two sets of values $A$ and $B$ and for each set I have a computable function from that set to a third set $C$. Now suppose that I want to construct a function from $A$ to $B$, such that if ...
2
votes
1answer
90 views

Is P/poly known to be in RE?

Is P/poly known to be in RE? If yes what other classes is it known to be part of.
0
votes
0answers
26 views

What's the class of problems solvable in polynomial time with an exponential number of processors?

What's the class of problems solvable in polynomial time with an exponential number of processors? I am asking this because I'm curious about the class of problems that could feasable be solved on a ...
0
votes
0answers
19 views

What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?

What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat? Would this result in their being a quasi polynomial-time algorithm for all NP-complete problems?
0
votes
0answers
17 views

proof that $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$

I came across this problem which asks to prove: $$NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$ for $S(n) \geq \log{(n)}$, with $S(n)$ being fully time-constructible... As an attempt, isn't the proof ...
0
votes
1answer
30 views

What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to

What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to? I suspect that their, NEXP, ESPACE and 2EXPtime respecitvely. And what bout $NP^{EXP}$
2
votes
0answers
31 views

Are there problems that are known to be in ZPP but not in p

Are there any problems that are known to be in ZPP but not in p?

1
2 3 4 5
35