News for hackers. Stuff that matters.

A comment on Sleeping Through the Technical Interview (2022). Parent comment

Re:Sleeping Through the Technical Interview (2022) by AshamedCaptain on Friday July 07, 2023 @03:42PM (#36637313)
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.
[ Parent | on HN ]
Re:Sleeping Through the Technical Interview (2022) by kadoban on Friday July 07, 2023 @05:52PM (#36638780)
As 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.

[ Parent | on HN ]
Re:Sleeping Through the Technical Interview (2022) by Tainnor on Sunday July 09, 2023 @05:28PM (#36659089)
> 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.

[ Parent | on HN ]
Re:Sleeping Through the Technical Interview (2022) by kadoban on Sunday July 09, 2023 @06:16PM (#36659526)
Yeah, 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.
[ Parent | on HN ]