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.
2,479
questions
0
votes
2
answers
69
views
How to prove that we can study the complexity of Recurrence Relations by always giving in input a power of how many children each node creates?
Let's say we have the following Recurrence Relation:
$$ T(n) = \begin{cases}
1 & n=1 \\
3T(\frac{n}{3}) + \Theta(n) & \text{otherwise}
\end{cases}
$$
I've been taught I can ...
- 7,847
0
votes
1
answer
1k
views
Determine if an NFA accepts infinite language in polynomial time
Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite.
(Note that converting NFA to DFA is exponential time).
For any DFA,...
CommunityBot
- 1
0
votes
0
answers
19
views
Finding the Optimal Palette for a Set of Images
Motivation
I want to draw pictures using indexed colors. As I have limited space for colors per-palette, I want to choose palettes in an intelligent fashion, based on the pictures I want to draw. The ...
- 1
1
vote
1
answer
134
views
Can someone help me fully grasp idea and time/space complexity with this code?
My understanding is the following:
Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first ...
CommunityBot
- 1
3
votes
2
answers
100
views
An algorithm that is $O(n^{\log(n)})$
After having searched for a while, and after having read this
https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities
I was just wondering: is ...
- 1,554
1
vote
1
answer
120
views
Most scalable distributed consensus mechanism based on message complexity?
One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity.
For example, PBFT message complexity is O(n^2) that ...
CommunityBot
- 1
0
votes
1
answer
176
views
Time complexity of merging two lists while preserving order
I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
CommunityBot
- 1
1
vote
1
answer
63
views
Reconstructing a string from two its partitions into substrings of varying size
Given two unordered partitions of the same string over a finite alphabet into substrings, how hard is it to reconstruct the original string? If multiple solutions exist, any one will suffice.
Under an ...
- 5,344
0
votes
1
answer
33
views
Complexity of generating all subsets of size $k$ using recursion
What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set?
...
- 27.1k
0
votes
0
answers
10
views
Computational complexity of some optimization problem? [closed]
I wonder if there are some methods I can borrow from computational complexity theory to analyze the optimization problem such as a convex optimization problem. An example of this is to find the ...
- 51
0
votes
0
answers
24
views
Problems in $DTIME(n\log n)$ [closed]
Let $DTIME(t(n))$ denote the complexity class of languages solvable in time $O(t(n))$ by a deteministic Turing machine with one tape. By the result of Kobayashi, we know that $DTIME(o(n\log n))=REG$. ...
- 101
0
votes
1
answer
78
views
Find the largest possible number not larger than some integer N and is the product of K consecutive primes
Source: Hanoi student competition of unknown year (Kì thi học sinh giỏi thành phố)
Additional conditions:
N is a positive integer in range [1, 2^64 - 1]
K is a positive integer in range [3, 10]
...
CommunityBot
- 1
2
votes
1
answer
53
views
Is GNFS quasi-polynomial-time?
Wikipedia states that the time complexity of the General Number Field Sieve (GNFS) is
$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\log N)^{\frac{1}{3}}(\log \log N)^{\frac{2}{3}}\right),$$
...
- 940
0
votes
2
answers
43
views
Modified Quicksort*
given array of size n, and a function called FindPivot which returns the median with a time complexity of O(n^(1.1)).
what is the worst case time complexity of quicksort using the given func to find ...
CommunityBot
- 1
0
votes
2
answers
221
views
Time complexity of a 2-heap question
The problem statement is pretty straightforward: given an array of integers and a window size, return an array of doubles of the median of each window.
$arr = 1, 3, 5, 10, 6, 9, 2$ and $k = 3$ would ...
CommunityBot
- 1
0
votes
0
answers
19
views
Recurrence relation for TSP using recursion
This is a Python algorithm using recursion to solve Travelling Salesman Problem, consider $G$ a complete graph:
...
- 101
0
votes
0
answers
15
views
If the polynomial hierarchy collapses to level 1, what is the significance?
Recently, I was studying polynomial hierarchy and found that many unsolved problems are related to it, such as $P=NP$,$NP=coNP$.
I would like to ask, if the polynomial hierarchy collapses, what does ...
- 195
0
votes
1
answer
44
views
0
votes
1
answer
55
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 ...
CommunityBot
- 1
1
vote
1
answer
20
views
Subquadratic multiplication of polynomials in the max-plus/tropical semiring
Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $(\mathbb{Z}\cup\{-\infty\}, \max, +)$ which is faster than the trivial one? I'm interested in the ...
- 2,195
1
vote
2
answers
48
views
How much does proving that a special case of a problem is NP-complete tell me about if the general problem is NP-complete?
Define a graph problem as follows. Given a graph $G$ and
two integers $c$ and $k$, delete $k$ nodes and all edges incident to them, such
that, in the remaining graph, every connected component has at ...
- 27.1k
2
votes
1
answer
48
views
Why is this proof that CHESS is in EXPTIME correct?
I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by ...
- 11.8k
0
votes
0
answers
35
views
Algorithm for detecting if H is a induced subgraph of G in O(n)
Say that I am given a graph $H$ and a graph $G$ where the maximum degree of $G$ is known. How can I use BFS to find out if $H$ is an induced subgraph of $G$ in $O(n)$ time?
My current take is the ...
0
votes
0
answers
36
views
Why is exponential time 2^n^k and not 2^n
Does 2^n describe a class of problems or is it considered polynomial?
- 101
0
votes
1
answer
68
views
Finding the length of the longest palindrome in the given array
The problem that I'm trying to solve is:
Given an array of length N, I want to find the length of the longest palindrome in the given array.
With palindrome, we refer to a word, phrase, or sequence ...
CommunityBot
- 1
2
votes
1
answer
57
views
What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?
A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This ...
CommunityBot
- 1
0
votes
2
answers
45
views
Can a program that terminates have a running time of infinity? (Or not have an upper bound)
Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound?
A (non-)...
- 1
0
votes
2
answers
32
views
Are there any other language classes of time complexity between the P language class and the NP language class?
$P$ is the language class that is decidable in polynomial time by a deterministic Turing machine.
$NP$ is a language class that is decidable in polynomial time by non-deterministic Turing machines and ...
- 19.9k
0
votes
2
answers
49
views
merging logn + 1 sorted subarrays
given array A of size $n$ which is made of $logn + 1$ sub arrays which are sorted,
I need to sort ASAP.
example of array : $A[500,501,3,8,100,1,2,9]$ as you can see, sub arrays are :$[1:2][3:5][6:]$
...
- 27.1k
4
votes
1
answer
362
views
Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?
Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree.
With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but ...
CommunityBot
- 1
1
vote
0
answers
28
views
Listing all subsets of size $k$ of $\{1,2,...,n\}$ with just $C \binom{n}{k}$ operations
I was wondering if it is possible to list all subsets of size $k$ of the set $\{1,...,n\}$ by performing at most $C \binom{n}{k}$ operations for a fixed constant $C$.
I did find a way to compute these ...
- 11
0
votes
1
answer
92
views
How to find average time complexity of backtracking algorithm?
Problem is to decide if it is possible to partition a given array nums into k partitions. I've written a brute force backtracking algorithm. How do we analyse this algorithm to calculate average ...
CommunityBot
- 1
4
votes
1
answer
126
views
Possibly Tractable Variation of Suguru Puzzles
I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation ...
- 37.3k
1
vote
1
answer
26
views
number of substrings in same position with same contents
L1 and L2 are two lists which only consist of X's and Y'...
- 692
0
votes
0
answers
21
views
Understanding how to assign complexity to functions
I'm having trouble understanding how to assign complexity to functions. As an example, let's take the following pseudo code of the COUNTING-SORT algorithm, taken from the book "Introduction to ...
- 111
0
votes
1
answer
32
views
Algorithm Asymptotic Analysis
I'm trying to solve this time complexity: 𝑇(𝑛)=2𝑇(𝑛−2)+𝑛 but having some challenges addressing the (-2) component. Any insights on this complexity?
Ended up with a section [2^2(1) + 2^(3)(2) + 2^(...
CommunityBot
- 1
1
vote
1
answer
21
views
Can Sutner's (1991) quadratic algorithm for testing reversibility of Cellular Automata be applied to 1-D CA with even sized neighborhoods?
Admittedly I haven't fully wrapped my head around the paper yet, but I'm curious if this algorithm can be adapted to say, a one dimensional cellular automata with two states, and an even sized ...
- 2,080
0
votes
1
answer
36
views
Design an algorithm with linear complexity
Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A.
Beyond the algorithm, what I can'...
D.W.♦
- 150k
2
votes
1
answer
3k
views
To find median of $k$ sorted arrays of $n$ elements each in less than $O(nk\log k)$
How do I efficiently find the median of $k$ sorted arrays each of length $n$? Note that the total number of elements will be $nk$. I know it can be done in $O(nk \log k)$ time using merge technique. ...
1
vote
1
answer
223
views
Runtime of weighted interval scheduling dynamic programming algorithm
Consider this implementation of a dynamic programming algorithm for weighted interval scheduling:
...
CommunityBot
- 1
0
votes
1
answer
44
views
Complexity of recursive function that calls itself with it's own return value
Given the following code:
int f3(int n)
{
if(n <= 2) return 1;
f3(1 + f3(n-2));
return n - 1;
}
I was trying to find the time complexity and I got this ...
- 7,847
2
votes
2
answers
76
views
Prove that $O(\sum_{i=0}^{h}{2^i\times(h-i)}) \sim O(2^h)$
I want to prove that, $$\sum_{i=0}^{h}{2^i\times(h-i)} \sim O(2^h).$$
I did come up with the below proof,
$$\sum_{i=0}^{h}{2^i\times(h-i)} \sim O(\sum_{i=0}^{h-1}2^{h-1}) \sim O(h2^h),$$
but as it is ...
- 1,554
-3
votes
2
answers
74
views
How to find the standard theta notation of this?
Hi i am practising standard theta notation:
How could i find the standard theta notation of the following :
2n + 3n^2(log n)^3 + 2
and
...
D.W.♦
- 150k
0
votes
0
answers
25
views
Are there efficient ways to check if large numbers are prime [duplicate]
I was recently playing around in Python, and I wrote a program to check if a given number is prime. It works by checking to see if its divisible by each number other than 1 leading up to itself. It ...
1
vote
3
answers
264
views
What time complexity relative to input size is that?
If an algorithm takes two numbers $b$ and $n$ and its input size satisfies $O(\log_2{n} + \log_2{b})$ plus its time complexity satisfies $O(b \log_{2}{n})$, what is the time complexity relative to the ...
- 7,847
0
votes
0
answers
14
views
P versus NP relative to a P-complete set
If one can prove $P^A \not= NP^A$ for a P-complete oracle $A$, does this imply
$P\not=NP$.
I believe, that $P\not=NP$ relative to a P-complete oracle would mean $P^P \not= NP^P$.
And it seems that $P^...
D.W.♦
- 150k
3
votes
1
answer
137
views
Range queries with O(N log N) build and O(1) query
I read somewhere that you can compute range queries in O(1) with O(N log N) preprocessing for any associative operation (but not necessarily invertible or idempotent). How do you do this?
I know this ...
CommunityBot
- 1
2
votes
0
answers
43
views
Proving the language 2-SIMPLE-PATH is in NL
The Question
I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c}
\mathsf{there\;are\;two\;different}\\
\mathsf{simple\;paths\;from}\;s\;\...
- 145
-4
votes
1
answer
36
views
Data Structure And Algorithm
Given any singly linked-list L storing n real keys, that is, each key in L belongs to
R, design an algorithm (either in words or in pseudocode) that computes the sum of the negative keys in L. What is
...
- 88
2
votes
2
answers
117
views
Find if a given number must be in a set that is closed under gcd and lcm with some given elements
Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated).
There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ ...
CommunityBot
- 1