| > No, it's a big cost every time you pass a threshold, which happens an infinite number of times, because big-O assumes numbers can be arbitrarily large. Yes, it happens repeatedly. But it's not a big cost on every operation. Instead, it's a bigger and bigger cost, that happens more and more rarely. Averaged over the run, it's insignificant. > As long as the max number size is orthogonal to the number of elements n, you can assume a bound on the time for an addition operation, and then it becomes a constant in your run-time expression with respect to n. But it isn't necessarily orthogonal. As you deal with more and more elements, it's probably true that those elements will get correspondingly large. But maybe they won't be! The point is, we've decided that that is not a significant issue, since it's not part of most algorithms involving addition. > All true, but the spec for big-O doesn't say "assume away stuff that doesn't matter in practice" Of course it does. Everything is built on axioms and assumptions; things that are relevant to the problem, and things that are not. > When you make inconsistent, varying assumptions between problems, you're not doing STEM anymore; you're doing memorization, the kind of thing STEM isn't supposed to be like. I have no idea where this came from, but it's neither relevant nor accurate. Every STEM field requires a significant amount of memorization, and any application of a STEM field requires understanding what is relevant to the discussion at hand, and what is not. The point of any system—Big O included—is to understand a problem. The cost of the hashing operation isn't relevant for understanding the performance characteristics of hash tables. Maybe your hashing function is O(log N), and so lookups are O(log N). Maybe your hashing algorithm is O(N^2), and so your lookups are O(N^2). Neither tells you anything about how your hash will perform. |