What does "non-pathological data" mean?

Problem Detail: 

I took an algorithms class on Coursera. The professor in the video about hash tables said that

What's true is that for non-pathological data, you will get constant time operations in a properly implemented hash table.

What does "non-pathological data" mean? Can you give some examples?

Asked By : Alexander Myshov

Answered By : babou

Pathological data is supposed to be data that makes things go wrong in some way for your intended computation. It can be called pathological when it is rare enough in actual uses, so that things work OK most of the time. This can sometimes be made mathematically more precise (for example with probabilities), but the use of the word pathological in often informal.

For example, tomato salad and ketchup are excellent food, except for pathological people, meaning those people who are allergic to tomatoes. It can actually kill in some cases. But people allergic to tomatoes are very rare so that tomato dishes are considered excellent, except in pathological cases.

There are many algorithms that, while having a worst case complexity above the optimal one, are on the average as good or better than worst case optimal algorithm. If you compare quicksort and merge sort, quicksort is time $O(n^2)$ while merge sort is $O(n \lg n)$ in the worst case. But people will often use quicksort, because they both are time $O(n \lg n)$ on average, and the space complexity is $O(\lg n)$ for quicksort and $O(n)$ for merge sort.

The fact that quicksort is as good on average may be attributed to the fact that the $O(n^2)$ time complexity actually occurs only on pathological (implying bad but rare) cases.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27707