Average case performance vs. Worst-case guarantee