# Questions tagged [worst-case]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
0answers
33 views

### When was the dynamic array first used as an example for amortized analysis?

I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
0answers
59 views

### Asymptotic time required to simulate a Turing machine M for k steps

Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps. Wikipedia's page on EXPTIME-complete says it takes O(k) time ...
2answers
3k views

1answer
346 views

### Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof? Are there other non-trivial examples of random self-reducibility? Is there a good reference?
1answer
143 views

### Number of different longest common substrings

Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common ...
2answers
418 views

### What are the current best upper bounds of #P?

#P is the class of counting problems for problems in NP. In other words, a solution to #P returns the number of solutions to a particular problem in NP. I'm wondering if there have been any studies ...
3answers
2k views

### Justifying asymptotic worst-case analysis to scientists

I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. ...
2answers
133 views

### How well can we do with this variable assignment problem?

Given in this problem is a set of values $0 \le c_{a,b} < n$, where $0 \le a < n$ and $0 \le b < n$. The problem is to find the following sum as quickly as possible: \sum_{a,b}{c_{a,b}x^a ...
1answer
762 views

### How close can we get to linear multiply, add, and compare (on integers)?

Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and ...
1answer
1k views

### What is the worst case of the randomized incremental delaunay triangulation algorithm?

I know that the expected worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in Computational Geometry) is $\mathcal O(n \log n)$. There is an exercise which ...