All Questions
Tagged with time-complexity or runtime-analysis
3,563 questions
1
vote
1
answer
25
views
Software that finds/proves runtime complexity of given code?
Is there software that can prove the runtime complexity of given code?
- 222
1
vote
0
answers
51
views
+50
How to approximate max and min of hydra game?
It was originally posted on MO. But don't got any answer.
Basic background:
A hydra is a finite rooted tree (with the root usually drawn at the bottom). The leaves of the hydra are called heads. ...
- 31
6
votes
2
answers
649
views
Is the smallest grammar problem over the singleton alphabet known to be NP-complete or ...?
I can't find straight answer on this via googling around. Can you provide a reference?
The smallest grammar problem over a singleton alphabet is to find the smallest CFG $g$ that produces one and ...
- 628
2
votes
1
answer
44
views
Comparison of time complexity for NFA and backtracking implementations of regex search
I followed this helpful blog "Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)" by Russ Cox. This link is got from Russ Cox, ...
- 223
0
votes
1
answer
85
views
Does a Polynomial-Time Algorithm for Graph Coloring Problem proves P = NP?
Recently, I came across a video introducing an algorithm (GAF) that computes the chromatic number of any connected, undirected graph in polynomial time.
So, what impact it has on P = NP?
- 21
0
votes
1
answer
71
views
are relational databases optimal in terms of time complexity and space complexity?
I did not find an answer to this question here on stack exchange. Are relational databases optimal in terms of time complexity and space complexity?Are there known lower bounds on the time complexity ...
user181006
1
vote
1
answer
34
views
What is the worst-case time complexity for sorting within a range?
Suppose I have numerical data that's certain to be within a particular range: say, integers between 0 and 100. I know radix sort can be used to sort them faster than $O(n \log n)$: sort them first by ...
- 7,186
0
votes
0
answers
26
views
2
votes
1
answer
48
views
Proving the lowest possible time complexity of traversing an array is $O(n)$
How does one go about proving that the lowest possible time complexity for traversing an array is $O(n)$?, it is easy to see that this is the case. But how could I formally prove that this is true?, ...
- 23
0
votes
1
answer
59
views
Is there a model of computation where counting to n takes O(2^n) time?
In the comments on this answer, another commenter says that the algorithm isn't polynomial-time in e, because it contains the following loop:
...
- 7,186
1
vote
0
answers
31
views
Asymptotic complexity of knapsack algorithm considering all numbers ∈ Z
In the knapsack problem, we consider numbers ∈ Z+ which gives us a run time of $O(nW)$. To my understanding, this is pseudo-polynomial and the worse case runtime is $O(n*2^{log(w)})$
My question is, ...
- 11
0
votes
1
answer
78
views
Algorithm for finding a 'mountain' with the tallest height in O(n) time
Here's the problem:
you get an array of numbers. lets say you get an array of 5 numbers: {5,3,4,1,1}. Each of the numbers in the array represent a 'tower'. Your goal is to make the array in the shape ...
1
vote
1
answer
93
views
Why is P = PSPACE, if P = NP?
I understand that we have the inclusions $P \subseteq NP \subseteq PSPACE$ . If we assume $ P = NP$ , this means that every problem in NP can be solved in polynomial time by a deterministic Turing ...
- 53
2
votes
1
answer
57
views
Sorting: worst-case time complexity best upper bound (Challenge)
Assuming a model of like multitape TM, (meaning do not assume O(1) time for operations or anything). Informally, what is the best known algorithm worstcase-wise (as a function of the input) for ...
- 123
3
votes
1
answer
765
views
Is minimal complexity unknown for most of the problems out there?
I'm using the term "minimal complexity" as the complexity of the best possible algorithm for solving a particular problem - in terms of, say, time, in O() notation.
For example, for matrix ...
- 165