You beat me to it ... if someone asks you for the complexity of a problem in Big-O notation, I'll always answer with the worst case. I suppose answering with t

You beat me to it ... if someone asks you for the complexity of a problem in Big-O notation, I'll always answer with the worst case. I suppose answering with the average performance is useful if the routine is going to run a lot, but you'd better be careful even with that ... if the worst case is orders of magnitude bigger than the average, it may still matter.