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
vote
0answers
45 views

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

In the previous question, I have found the number of different solutions to the problem of finding n-tuples of naturals greater than 1 with bounded product: $$\begin{align}0<\prod_{i=1}^nk_i\...
0
votes
0answers
13 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
35 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 ...
2
votes
2answers
74 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 ...
2
votes
0answers
43 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
15 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 ...
0
votes
0answers
32 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
vote
1answer
37 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
1answer
39 views

What time complexity is a reachability algorithm?

I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive ...
-1
votes
1answer
63 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
29 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 ...
1
vote
2answers
35 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 ...
0
votes
1answer
270 views

heap data structure complexity

I'm trying to count running time of build heap in heap sort algorithm ...
0
votes
1answer
22 views

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

I have the following function. ...
2
votes
2answers
83 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, ...
4
votes
1answer
1k views

Can we create faster sort algorithm than O(N log N)

I was thinking that we can create algorithm for sorting that will work faster than $O(N\log N)$ Let's say we have given array $A$ consisting of $N$ integers, where $N = 10^6$. Our task is to sort ...
0
votes
1answer
24 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
1answer
49 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
16 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 $...
1
vote
1answer
36 views

Using Subset Sum algorithm $O(n)$ times to find the subset

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
0
votes
1answer
173 views

Is time complexity of the greedy set cover algorithm cubic?

I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements....
2
votes
3answers
62 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
47 views

What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
1
vote
1answer
24 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
2answers
137 views

Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?

I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric. An obvious approach is to make all $...
0
votes
0answers
11 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
20 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
25 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
21 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
25 views

Best case for sorting algorithm

Given this sorting algorithm: ...
1
vote
2answers
373 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
1
vote
1answer
38 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.
0
votes
1answer
42 views

What is the time complexity of finding the FIRST and FOLLOW sets?

Given how important these are for parsing, I'm surprised I wasn't able to find anything about their complexity. I'm interested in all combinations of: What is the (edit: best known) time complexity ...
1
vote
1answer
31 views

Big theta notation

I'm trying to figure out the following problem: If algorithm $A$ has a big theta notation of $n^3$ and algorithm $B$ has a big theta notation of $n^2$, there might be an infinite number of ...
0
votes
7answers
277 views

What is the time complexity Big-O of this algorithm?

What is the time complexity Big-O of this algorithm? , The first assumption it's O(N * lg N) but it is not correct, why? ...
0
votes
1answer
42 views

How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?

I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^*(2^{n/2})$? ...
0
votes
0answers
8 views

Logic of the squared running time in “A Variant of Nondeterministic Acceptance”

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman, Motwani where I came across the following claim: A Variant of ...
0
votes
0answers
16 views

Applying Polynomial Time Approximation Scheme (PTAS) on an Algorithm

I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-ϵ) and (1+ ϵ) in the running time of the algorithm but I don’t ...
0
votes
1answer
30 views

Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question

hope you all are doing well. I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien....
4
votes
2answers
48 views

Does time or space complexity of arithmetic operations get affected by the number of digits?

Suppose I have two 5-digit numbers (A and B) and two 50-digit numbers(C and D). Do the operations A+B and C+D have equal complexity in terms of time and space? or C+D is more complex due to the size ...
6
votes
1answer
2k views

Tree decomposition - Fastest algorithm in practise

I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph. I found the paper "A linear time algorithm for finding tree-decompositions of ...
0
votes
1answer
56 views

Is this computational complexity of the k-NN (custom distance) correct?

I read on a book that in general k-NN (no optimizations), given $d$ dimensions $n$ examples every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
3
votes
1answer
163 views

“Fuzzy” Chinese Remainder Theorem

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&\equiv a_3 \mod 7 \...
-1
votes
1answer
110 views

Time complexity problem

Let Σ = {0, 1} and let A ⊆ Σ* be a language contained in DTIME(4n), and define B = {xx | x ∈ A}. (a) Show that B ∈ DTIME(2n). (b) Prove that A ≤pm B. I'm new to complexity theory. how can I show ...
1
vote
1answer
48 views

Can radix sort reach exponential time complexity?

For example, assume the input array is $$[121212,212121]$$ Say we are in base 10, so count sort will work in $O(n)$ time. We have 6 iterations which is approximately $n^2$. Is this a worst case ...
0
votes
1answer
37 views

Time complexity of DFS and recurrence relation

Is it possible to compute time complexity of Depth First Search (recursive version) which is O(E+V) using a recurrence relation?
0
votes
1answer
41 views

Efficient algorithm to compare arrays problem

I was submitted an interesting problem, but I wasn't able to find a solution. Define a function p(x, y) that takes int x and y, with ...
2
votes
1answer
26 views

What is the difference in time-complexity for sorting these 2-d arrays?

Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements. It is given that each row is sorted in ascending order, Can you sort ...

1
2 3 4 5
34