Optimal Average Case Sorting on Arrays.

Manfred Kunde Rolf Niedermeier Klaus Reinhardt Peter Rossmanith

Published in: STACS (1995)

Keyphrases

average case
worst case
worst case analysis
competitive ratio
learning curves
upper bound
uniform distribution
lower bound
vc dimension
greedy heuristic
decision trees
np hard
scheduling problem
optimal strategy