Problems with these approaches

• worst case complexity:

  • a low worst case is fine
  • but performance with a bad worst case is often much better in practice
  • therefore worst case analysis is often too pessimistic