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
-1
votes
1answer
56 views

Quasilinear time algorithm for 3-SAT

Is it consistent with the current knowledge that there is an algorithm solving a 3-SAT instance in $n$ clauses in quasilinear time in $n$?
-1
votes
1answer
43 views

what is the time complexity of this for for for if

I need to know the analysis of time complexity of this case? ...
0
votes
1answer
278 views

Best algorithm to find "deepest" interval

Let's say I have a list of intervals on a number line. The "depth" of a point on this number line corresponds to the number of intervals in the list that contain it [the point]. So for ...
3
votes
0answers
34 views

Computational Complexity of 3SAT variant with additional restrictions on variables/clauses

Given a 3SAT problem with the additional constraints that: No clause or set of clauses is the 3SAT instance is 'redundant'. Thus, this 3SAT cannot eliminate any clauses. For any/every clause, the ...
1
vote
2answers
39 views

Disambiguating Big-O and Theta for Expressing Time Complexity

Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ? Can ...
1
vote
1answer
33 views

CVAL is in P (technical detail)

I would like to clarify to myself the way that an algorithm that proves the statement in the title works: I think the idea should be like this: We assign the input values to the bit nodes We ...
1
vote
1answer
44 views

Why can't we use BFS with modifications to find shortest paths in weighted graphs

I came across this post about how we can get to all shortest paths from source (u) to destination (v) . If the algorithm is working in O(E + V), why can't we use it (after slight modifications) for ...
1
vote
1answer
33 views

Determine the time complexity of this algoritm (pseudocode)

{ t <- n while t>1 do t <- log_2(t) } I tried to do it this way: $f^\text{(1)}(t)=\log_2(t) \\ f^\text{(2)}(t)=\log_2\log_2(t) = \log_2^{(2)}(t) \\f^\...
0
votes
1answer
45 views

Time Complexity Analysis When Merging Routes in Vehicle Routing

I would like to know the best way to approach the time complexity analysis of the following algorithm. I have come up with 2 approaches so far. We have a ...
1
vote
0answers
29 views

How is red-black tree insertion more effective than avl tree insertion

I'm having trouble understanding why RB tree insertion is called more effective in all sources. It's said that AVL trees require "more rotations" than RB trees, but from what I've learned I ...
1
vote
1answer
64 views

Is this divide-and-conquer algorithm O(n)?

Yesterday I came up with a divide-and-conquer algorithm about all subarrays of length k of an array of length n. Outline: ...
0
votes
1answer
12 views

Polynomial-time algorithm for distribution of arbitrary symbols

Is there a polynomial-time algorithm for distribution of clauses of arbitrary symbols (i.e. similar to multiplication distributing over addition)? For simplicity, let's assume the distributive ...
1
vote
1answer
28 views
0
votes
0answers
47 views

Optimal Word Guessing Algorithm in $O(n \log n)$

Say that your friend picks a word $(w_1, w_2,\dots,w_n)$ according to a known probability distribution $(p_1,p_2,\dots,p_n)$. You ask yes or no questions until you are certain which word has been ...
2
votes
1answer
55 views

Best algorithm for solving $A[i] + B[j] = m$

Suppose $A$ and $B$ are arrays of real numbers of length $n$, and $M$ is another real number. One algorithm for finding indices $i$ and $j$ such that $A[i] + B[j] = M$ is to comparison-sort $B$ and ...
0
votes
2answers
33 views

How does a hash table not require all the keys to be looked through to find a value, i.e. O(N)?

Before starting, I want to say that I understand time complexity, and I understand how a hash table is considered O(1) vs an array having a time comp. of O(N) in terms of what you learn. What I don't ...
0
votes
1answer
27 views

How can I develop an algorithm to schedule production?

Given an an table that contains products I am selling with the dates, and given a table that contains the possible work orders with each work order, arrange the work orders such that all items are ...
1
vote
3answers
137 views

What could be the most efficient algorithm to compare two unsorted arrays?

I have two arrays A and B of the same length n. I am looking to swap such that all the elements of array A are less than each element of B. Elements in A and B can be unsorted. Example Inputs: ...
0
votes
0answers
48 views

Accurately determine the real 'hardness' value of any given input instance for subset sum

Assuming the 'hardness' of any possible input instance with $N$ elements (of any bit length) for the subset sum problem could be represented as $H \in \{0,0.000001,0.000002 \dots, 1 \}$, being ${0}$ ...
1
vote
1answer
17 views

The Turing Machine in the proof of Time Hierarchy Theorem

In the proof of the Time Hierarchy Theorem, Arora and Barak writes: Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
1
vote
0answers
43 views

finding max element in a min-max heap structure

I am trying to implement min-max heap structure A min-max heap is a data structure that is identical to a binary heap, but the heap-order property is that for any node, X, at even depth, the element ...
-2
votes
1answer
29 views

understanding complexity of a function with defined function

this is the algorithm : ...
0
votes
2answers
97 views

Complexity of sorting $k$-sorted array using QuickSort and HeapSort

Given a $k$-sorted array where each element in the array is $k$ positions from its correct position, we want to sort such array using quick sort. Generally speaking, I understand that running time is ...
0
votes
0answers
17 views

Binning a set into subsets deterministically

I have an unordered set of n unique, positive integers. I want to partition it into ceil(n / k) unordered sets of up to ...
0
votes
0answers
50 views

Finding the Solution out of N possibilities

Suppose there are 10 (4x4) matrices, where the elements in each matrix are dependent on one variable ($\theta$) non-linearly. All the matrices are independent of each other, so there are 10 $\theta$s (...
1
vote
1answer
49 views

What is the Runtime of this recursive algorithm?

I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in ...
0
votes
4answers
92 views

How can I compare two algorithms using their Big-Oh complexities?

I have two recursive algorithms to solve a particular problem. I have calculated their time complexities as $O(n^2\times\log n)$ and $O(n^{2.32})$. I need to find which algorithm is better in terms of ...
0
votes
1answer
30 views

How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
-1
votes
2answers
61 views

What is the the greatest thing a computer has trouble doing?

If we have all these optimized programs for very specific tasks, what would be the antithesis of them? I've asked a programmer friend of mine, and they thought a good answer had to do with multi-...
2
votes
0answers
34 views

Kolmogorov complexity of probability distributions, with and without time bound

Kolmogorov complexity of a string is the length of the shortest algorithm that generates it. Here I'm focusing instead on randomly distributed strings $x$, with length $n$, with a probability ...
2
votes
1answer
28 views

Do graphs with a bounded number of incident edges have a polynomial-time subgraph-isomorphism algorithm?

It is well known that the subgraph isomorphism problem is NP-complete. And so a polynomial-time algorithm for solving it would mean P = NP. Thus I'm interested in whether a bounded version of the ...
1
vote
1answer
108 views

Why is the space complexity of finding anagrams in a string O(1) instead of O(n)?

In the problem find-all-anagrams-in-a-string, one tries to find all anagrams of a string $p$ (of length $k$) in a string $s$ (of length $n$) and return a list of the anagrams' starting indices. The ...
0
votes
1answer
31 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
37 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
40 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
13 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
33 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
23 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
18 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?
0
votes
1answer
30 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
105 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
17 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
65 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
82 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 ...
-1
votes
1answer
49 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
73 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
87 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
71 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
104 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
33 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 ...

1
2
3 4 5
44