Re:Go maps don't appear to be O(1)
by mindslight on Thursday October 01, 2015 @09:13PM
(#10315976)
I totally agree but for one point - seek() in a file is probably O(log <filesize>). So he wasn't even right in his own context...
Right, but the point is, even under the assumption of constant seek times, he didn't seem to get that "doesn't not depend on x" is the same as "constant [implicitly taking the only relevant parameter to be x]".
What's not fine is selectively making that assumption without being aware of it, resulting in a situation where the kewl kids recite back "hashtables are O(1)" with no understanding of why, or what different assumptions you have to make to get there, resulting in an exception-laden body of knowledge. That's not what rigor looks like.
One time I was asked for the run time of a random-line-getter function for a file that seeks to a random byte and fans out to the line breaks. I said, "well, that would depend, not on the file size, but the line length, and it would be linear in that."
He "got me": "Wrong, it's constant." Indeed, if you implicitly assume that relevant parameter is file size, and don't understand the implications of "does not depend on ...", then you can compare answers against an answer key and regard someone as wrong for not saying exactly that.
"Hashtables are O(1)" results from exactly that lack of rigor, where it's all a game of which password to spit back, rather than "can you identify the constraints on solving this problem?"