WikiSort – Fast, stable, O(1) space merge sort algorithm

Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by jmpeax on Wednesday March 26, 2014 @08:39PM (#7477780)

This is incorrect, under deliriums pedantic interpretation of space complexity. Some regular expressions require one to accept a certain number of examples of a character. This means that storage space for the count is required, which scales logarithmically in the count.

[ Parent | on HN ]

Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by repsilat on Thursday April 03, 2014 @04:02AM (#7521501)

This is why my comment began with the words "particular, individual". A regex like (1{5}0{3})\* can be implemented in constant space, but a language like

    matches(n, m, string):
        return matches((1{n}0{m})\*, string)

cannot.

Just think about it -- the former is just a DFA, and so of course you can do it in constant space (provided your input stream is abstracted away, or you use a TM.

[ Parent | on HN ]