Worst-Case Running Times for Average-Case Algorithms.

Luis Filipe Coelho Antunes Lance Fortnow

Published in: Computational Complexity Conference (2009)

Keyphrases

worst case
average case
running times
worst case analysis
upper bound
error bounds
lower bound
times faster
greedy algorithm
np hard
approximation algorithms
computational complexity
uniform distribution
online algorithms
vc dimension
learning curves
sample size