No mention of previous work = reject?

One of the key questions for any piece of scientific work is this: how does this work contribute to human knowledge?

If a work fails to even discuss its relationship to prior work, then it is entirely appropriate to reject it. Likewise, if the authors mention algorithms that are directly comparable but fail to actually make a comparison with any of those algorithms. When I am given a paper that is entirely isolated in this way, I will not even bother to check the details of the algorithm's soundness, since the work already has a major disqualifying failure.

For many algorithms, however, the differences are qualitative and not quantitative, and thus a direct comparison would be unenlightening or pointless. For example, if algorithm X tolerates a class of failures that prior algorithms do not, then it is enough to show that algorithm X tolerates those failures. One does not necessarily need to re-prove or empirically demonstrate that the others do not.

Likewise, the number of potentially related prior works is often vast and complicated. No algorithm paper will ever compare to all of the other related algorithms, because "related" is a broad and fuzzy concept. You and the authors will generally not make the same judgements about which algorithms might be interesting to discuss in related work or to directly compare against. Thus, the standard to which you should hold related work is not "Do I want to see comparison against Algorithm Y?" (that's Evil Reviewer #2 behavior) but rather "Does the comparison provided sufficiently support the author's assertions?"

Bottom line: be generous in your judgement of comparison to prior work, but papers with no meaningful comparison should be rejected.

Needs revision

There is a meaningful difference between asserting that a particular work is fundamendally not appropriate for this venue, or that it is unacceptable as it now stands. The former is a 'reject', the latter is 'accept with revisions required'.

You should recommend a rejection if the changes required to make it a good, appropriate paper would require to fundamentally change the paper itself or its conclusions. According to your description it's not necessarily the case - you claim that the paper needs a comparison to existing techniques on both a methodological level and also on the level of results. If the paper added these comparisons, would the paper be acceptable, or would it still be not good enough? That's what the review should state.

You can write: the algorithm is sound and their method is thorough, however, there's no mention of the various related previous works (e.g., X, Y, and Z) which address the very same issue, without such discussion I cannot evaluate the work's novelty and I must reject the paper at this time.