3 ms·
Well they were indeed sleeping through the interview. Otherwise I don't know how could one possibly claim that a program whose first statement is a sequential l
by AshamedCaptain 3y ago
Well they were indeed sleeping through the interview. Otherwise I don't know how could one possibly claim that a program whose first statement is a sequential loop over all values of the input has "constant time" asymptotic complexity.
- kadoban 3y agoAs with everything in algorithm analysis, it depends on your model of computation. That is, it depends what you're counting. For sorting (comparison sorts), one fairly typical model is to just count how many comparisons you do. Which, this does none (kind of, not really, they're really just implicit or hidden in the OS). It's just playing around with computational models, not a serious proposal. It's either just a joke, a troll, or an parable about the need to be careful about what metric you're measuring. Or some combination of those.
- Tainnor 3y ago> Which, this does none Neither does bucket sort, and nobody has claimed that bucket sort is constant in time. We only count comparisons in typical sorting algorithms because we know that the overall complexity is proportional to it.
- kadoban 3y agoYeah, that's kind of the point I was trying to make. It's an innapropriate compuational model, so the answers you get out aren't meaningful.