3 ms·
> 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
by DanWaterworth 10y ago
> 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.
- tantalor 10y ago"Not even wrong" https://en.wikipedia.org/wiki/Not_even_wrong https://en.wikipedia.org/wiki/Not_even_wrong
- Retric 10y agoEhh, 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.