Hacker News Reader

> You'll know that iterating through a linked list is O(N), binary search is O(log(N)) and a hash table lookup is O(1). What if I told you that all of the above is wrong?

It's not wrong, it doesn't have enough contextual information to be right or wrong.

View on HN

"Not even wrong" https://en.wikipedia.org/wiki/Not_even_wrong

Ehh, his assumption is that O notation should say something at lower bounds, which is simply wrong. He should be testing 10-15+ GByte data structures not < MB data structures.

Consider, O(X * Log (X)) is generally thought of as good. But, let's assume the algorithm takes 24 hours + x * log(x) nanoseconds. Well for low values of X that 24 hours is going to be a pain and it's going to look like constant time, but for really really big data sets x * Log(x) will actually dominate.

Reply on news.ycombinator.com