Problems with these approaches

• average case complexity:

  • average case complexity assumes uniformly distributed input
  • but this is not typical in practice:
  • average case analysis tends to be too optimistic