# Questions tagged [worst-case]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
1k views

### Did “Where the really hard problems are” hold up? What are current ideas on the subject?

I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually ...
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. ...
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 ...
3k views

172 views

### Worst-Case and Average-Case running-time equal with universal p-distribution with kolmogorov-complexity any applications of this theory?

at the moment I'm reading "Gems of Theoretical Computer Science" from Schöning and Pruim. In Chapter 8 the book defines a "universal probability distribution" in a way that the Average-Case running-...
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 ...
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 ...
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 ...