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
3answers
102 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. ...
0
votes
1answer
45 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
12 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
19 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
27 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
37 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
110 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
31 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
vote
1answer
14 views

Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have $$ NSPACE(S(n)) \subseteq DSPACE(S(n)^2) $$ Am wondering, what happens if $S(n)$ is fully time-...
1
vote
0answers
78 views

What are some of the most ridiculous claims in computer science that we haven't disproved?

What are some of the most ridiculous possible claims in computer science that we haven't disproved? E.g. For example the claim that ZPP=exptime is absurd but has not been disproven.
0
votes
1answer
23 views

Is this algorithm for Exact Three Cover sub-exponential, because I find $length(s)/3$ combinations for $C$?

Given an input $S$ (set of elements) find an exact three cover for a list of 3-element sets named $C$. $S$ = 1,2,3,4,5,6 $C$ = [1,2,3],[4,5,6],[3,1,2] Algorithm 1.Sort list and delete occurrences of ...
1
vote
1answer
28 views

What would be the practical consequences of ZPP=exptime

What would be the practical consequences of ZPP=exptime. It would be pretty ridiculous if the was true but what if it was?
0
votes
1answer
35 views

How is the NP verifier polynomial?

If we start with the definition of L being in NP if "there exists a polynomial NTM that decides L" (where polynomial for an NTM means the length of the worst run as a function of the size/length of ...
0
votes
0answers
7 views

On the complexity analysis of weighted quick union in algorithms 4th edition by Sedgewick and Kevin Wayne

I've been studying Sedgewick's book and tried to count the number of array accesses for weighted quick union in the worst case. There is a diagram for this on the left side of page 229 in the fourth ...
1
vote
1answer
44 views

How to solve recursion T(n)=T(n/2)+T(n/3)+n?

How to solve recursion $T(n)=T(n/2)+T(n/3)+n$? I do not really know how to approach this kind of recurrence.
1
vote
1answer
63 views

how to reduce the time complexity of this code?

I have a graph G=(V,E). A list of nodes NODE subset of V. I want to find out all the ...
1
vote
1answer
102 views

Time complexity of a recursive enumeration in the problem of finding n-tuples of naturals greater than 1 with bounded product

I have to determine the time complexity of a recursive enumeration in the problem of finding n-tuples $(k_i, ..., k_n)$ of naturals greater than 1 with product less or equal to $K$. Problem can be ...
2
votes
0answers
63 views

Filling a hole in an image in O(nlogn)

I have a grayscale image (given by a float matrix with values between [0, 1]) with a hole in it (a cluster of pixels/cells with values of -1). Definitions: The ...
0
votes
0answers
24 views

Balanced vs Unbalanced KD-tree range search/query complexity

I'm currently reading up on the time complexity of the range search/query for an unbalanced KD-tree. I see all these different articles where the same the complexity is O(sqrt(N)) where N is the ...
2
votes
2answers
75 views

Efficient way to reduce a binomial coefficient as a fraction

Here is the full problem. You need to calculate Euler's totient function of a binomial coefficient $C_n^k$. Input The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$. ...
1
vote
1answer
49 views

Time complexity of code running at most summation(N) times in a loop

Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration: ...
0
votes
0answers
33 views

How to calculate time complexity of KD-tree data structure [duplicate]

I have made a KD-tree data structure for a project I've been working on. But I can't seem to figure out the query complexity for it. What I know: I know that KD-tree is using BST structure, so for a ...
-1
votes
1answer
71 views

what is the time complexity of this code

what is the time complexity of the following code. please help me. // a is mxn matrix ...
1
vote
2answers
46 views

Complexity of recursion T(n) = 2T(n-1) + C?

I am trying to calculate the Time Complexity of the Recursive Function, suppose this, function T(int n){ if(n == 1) return 1; return T(n-1) + T(n-1); } the ...
1
vote
3answers
48 views

Linear Programming Problem - what is feasible size for solution on a PC

I need to get feeling for the feasible size of a LPP, that can be solved on a PC. Say, its a good one (8 cores @ 3+GHz, 64GB RAM). We also assume that number of variables is close to the number of ...
0
votes
1answer
23 views

Big-O: Why is the time complexity of these loops O(N)?

I have the following function. ...
0
votes
1answer
28 views

Counting occurrences of word in a text

Let's say I have a long text of 1M words and I would like to create a table of all the words ordered by the number of occurrences in the text. One approach would be populating a dynamic array with ...
2
votes
2answers
84 views

Managing an hotel using AVL trees - Data Structures

I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$ and it can be occupied or not. Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, ...
2
votes
1answer
50 views

Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to. In the 2-dimensional case it's fairly ...
0
votes
0answers
16 views

Translating running times of $3$-coloring to $k$-$SAT$ complexity

Suppose there is an $O(f(n))$ algorithm for $3$-coloring a graph on $n$ vertices what does it translate to in terms of time complexity for solving $k$-$SAT$ with $m$ clauses?
1
vote
1answer
19 views

Importance of space constructability in time space relation in complexity

I am reading Arora-Barak's Complexity book. In Chapter 4, they state and prove the following theorem. Why $S$ should be space constructible? Wouldn't all three containments of theorem hold, even if $...
2
votes
3answers
63 views

Little O notation relationship

Given the functions $𝑓(𝑛)=𝑛^{n}$ and $𝑔(𝑛)=10^{10n}$, I am trying to establish the following relationship: $𝑓(𝑛)\notin o(𝑔(𝑛))$. I know to show for the opposite, $𝑓(𝑛)\in o(𝑔(𝑛))$, I ...
1
vote
1answer
25 views

Is $P$ defined for TM which decide or accept a language?

Sipser defines $TIME(t(n))$ as the set of all languages that are decidable by an $O(t(n))$ time TM and then $P = \bigcup_k TIME(n^k).$ However I see also many definitions like $$ P = \{ L \mid \text{...
0
votes
0answers
12 views

Time complexity of the given function

I made a function which returns the number of divisors that are divisible by two. I already new the formula for the total number of factors of a given number, so we remove one 2 from the factorization ...
1
vote
2answers
24 views

Show that the best case time complexity of Quicksort is $\Omega(n \log n)$

I am trying to show that the best case time complexity of Quicksort is $\Omega(n \log n)$. The following recurrence describes the best-case time complexity of Quicksort: $$T(n) = \min_{0 \le q \le n-...
1
vote
1answer
26 views

Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$

The recurrence form of bubble sort is $T(n)=T(n-1)+ n- 1$ How can I prove by induction that this is $\Omega(n^2)$? I'm stuck with $T(n+1) \geq cn^2 + n = n(cn+1)$
0
votes
1answer
23 views

Time complexity analysis of 2 arbitrary algorithms - prove or disprove

We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size. We denote the worst time complexity of each ...
1
vote
1answer
35 views

Best case for sorting algorithm

Given this sorting algorithm: ...
1
vote
1answer
39 views

Finding a closed formula for recurrence relation

I'm trying to find a closed formula for the below recurrence relation: For the first one, $n$ is some power of 2 $$T(n) = \begin{cases} 4 & \text{if $n=1$} \\ 2T(\frac{n}{2}) +4 & \text{...
3
votes
2answers
39 views

What is $2^{O(n)}$? [duplicate]

How can I interpret a time complexity of $2^{O(n)}$? Is it simply equal to $O(2^n)$? I'm pretty new to this, so would appreciate any kind of help.

1
2
3 4 5
36