4 ms·
Facebook's implementation would still be constant time for short strings, because there's a constant which bounds the runtime. Though I hear that the definitio
by epistasis 7y ago
Facebook's implementation would still be constant time for short strings, because there's a constant which bounds the runtime.
Though I hear that the definition of big-O notation has shifted a bit in Silicon Valley these days so maybe that answer would get me in trouble in an interview.
- ryani 7y agoIt's true that big-O notation only concerns behavior with large N, but it's a bit disingenuous to say that the loop executes a constant number of times -- by that argument, you could say that if you implemented size() by strlen() it's O(1) because the string must be less than 2^64 bytes long on a 64-bit machine. So I can see why someone would claim that implementing size() via strlen() "only" for small strings shouldn't be considered O(1), because strlen() is O(n) and within that class of strings the runtime is increasing as the length increases.
- coolplants 7y agoI think it’s a bit more disingenuous to compare the magnitudes of 2^64 and 23 for the sake of argument, as if 2^64 isn’t practically asymptotic.