Re:WikiSort – Fast, stable, O(1) space merge sort algorithm
by tomp on Saturday March 15, 2014 @08:21PM
(#7407190)
But this is a really irrelevant point, as you can't even represent an array of size n without log n space (for the start pointer and the size/end pointer). So, every algorithm involving arrays needs at least log n space, if nothing else for the input arguments.
[ Parent
| on HN ]
Re:WikiSort – Fast, stable, O(1) space merge sort algorithm
by _delirium on Saturday March 15, 2014 @09:04PM
(#7407326)
It's irrelevant in practice, mostly because log(n) is very small for essentially all values of n, so one could consider it "close enough to constant". Close enough in the sense that a reasonably small constant (like "64") bounds any value of it you could possibly encounter in a sorting algorithm. But that's true of many things in big-O analysis.
If your temporary space was used by some indices represented as unary-encoded integers (which take O(n) space), it'd suddenly be harder to ignore the indices, because O(n) is not "very small" for many commonly encountered sizes of n. So I don't think taking the temporary space used by indexing into account is conceptually wrong, it just happens not to matter here because log(n) factors often don't matter.
Re:WikiSort – Fast, stable, O(1) space merge sort algorithm
by makomk on Sunday March 16, 2014 @07:15AM
(#7409016)
In practice, though, it makes sense in this case to assume integers representing array indices are constant-space and arithmetic on them takes constant time. The computers we're running these algorithms on use base 2 and the size of integer they can operate on in a single operation has scaled nicely with the amount of storage they have access to.