23 votes

When have we found better bounds for known algorithms?

The Union-Find algorithm, which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia,...
12 votes

When have we found better bounds for known algorithms?

The algorithm of Paturi, Pudlák, Saks and Zane (PPSZ) for $k\text{-} \mathrm{SAT}$ had been known to have a running time of $O(1.364^n)$ for $3\text{-}\mathrm{SAT}$, with a better bound of $O(1.308^...
11 votes
Accepted

Random walk and mean hitting time in a simple undirected graph

I have decided to ask David Wilson himself, soon thereafter got a reply: For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the barbell graph, ...
  • 311
8 votes

When have we found better bounds for known algorithms?

The Logjam Attack mentions that analysis of the general number field sieve (as applied to computing discrete logarithms over $\mathbb{F}_p$) descent step was tightend, see top left of the 3rd page. As ...
  • 778
6 votes

When have we found better bounds for known algorithms?

Recent work of Anupam Gupta, Euiwoong Lee, and Jason Li [1] shows that the Karger-Stein algorithm for the minimum $k$-cut problem has, in fact, asymptotic time complexity $O(n^{k+o(1)})$, improving ...
  • 4,361
6 votes

When have we found better bounds for known algorithms?

The work function algorithm for $k$-server was shown to be $(2k-1)$-competitive by Koutsipias and Papadimitrou - the algorithm was known previously and analyzed only in special cases. It is ...
5 votes

Travelling sales man with Quantum Computers

The set of problems that can be solved by an universal quantum computer in "polynomial time" (with at most 1/3 probability of error) is called BQP. Travelling salesman problem is in complexity class ...
4 votes

When have we found better bounds for known algorithms?

The $3$-Hitting Set problem had a few iterations of "better analysis" (see Fernau's papers [1] [2]) The algorithm before these paper had some arbitrary choices (like 'choose an edge'...), but when the ...
  • 1,237
4 votes
Accepted

Complexity analysis on a parameterized recurrence relation

First, if $k(n)$ and $T(n)$ are non-negative functions satisfying $$T(n)=3T(n-1)-T(n-2)+T(n-k(n))+3^{k(n)}\tag{$*$}$$ for all sufficiently large $n$, it is easy to see that $T(n)$ cannot have a finite ...
3 votes

How to treat dynamic memory allocation in algorithm analysis?

You want to read Wilson et al., Dynamic Storage Allocation: A Survey and Critical Review, 1995 and references therein, especially those to papers by Robson. Here is a quote that answers your ...
  • 4,746
3 votes

Random walk and mean hitting time in a simple undirected graph

In a recent paper, we found an mn upper bound (no big O) on the expected number of "cycles popped" by Wilson's algorithm and it is tight up to constants. It doesn't directly answer the question of ...
  • 375
2 votes

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time ...
2 votes
Accepted

Proof techniques for string algorithms?

There is some work on developing an algebraic or grammar-based view of string algorithms, for example Robert Giegerich, Carsten Meyer, Peter Steffen: A discipline of dynamic programming over sequence ...
2 votes

How is additive error handled in this simple algorithm? 'Product of all elements'

Use Taylor series expansion for the function $\prod_{i=1}^{n} (u_i + y)$ around $y=0$ to obtain the error as $\epsilon (\prod_{j=1}^{n} u_j) \sum_{i=1}^{n} u_i^{-1} + O(\epsilon^2)$. Note that Taylor ...
2 votes
Accepted

What is the state of the art research in analysing algorithms on GPU architectures?

research into GPU algorithms continues and it is well suited to some problems, but some of the initial excitement may be wearing off after lackluster results and difficulty of translating problems ...
  • 10.9k
2 votes

How to treat dynamic memory allocation in algorithm analysis?

Just allocating memory without touching it is very cheap. The cost should be negligible in any kind of theoretical algorithm analysis. You pay the serious penalty the first time you touch each page. ...

Only top scored, non community-wiki answers of a minimum length are eligible