News for hackers. Stuff that matters.
Re:Gaming CS Interviews by felixr on Wednesday September 28, 2022 @04:19AM (#33005506)
> a sorting algorithm may take O(n log(n)) runtime which is pretty common but be able to operate on an array in-place, only requiring O(n) storage.

If it's in-place the sorting might only require constant space and it can be O(1 ) [edit: in terms of space complexity]

Re:Gaming CS Interviews by unwind on Wednesday September 28, 2022 @05:02AM (#33005905)
Did you mean O(n)? It seems hard to sort n items without at least touching all of them once, which would make the time complexity linear (O(n)) instead of constant (O(1)). Or are you talking about storage needs? Then it sounds very hard to go sub-linear ... I'm confused.

I'm certainly not a good theoretical computer scientist, but I did quickly google this and I couldn't find any trace of constant-time sorting (unless you goalpost it to have O(n log n) processors, but that is kind of cheating, here).

Re:Gaming CS Interviews by Twisol on Wednesday September 28, 2022 @05:11AM (#33005968)
The fiddly detail here is that big-O notation can be used to measure the usage of any resource, not just time. The poster above noted that an in-place sort might have constant space complexity -- although this only makes sense if you discount the space required for the input anyhow (which is literally linear in the input size!).

Wikipedia distinguishes two measures of space, "total" (including the input) and "auxiliary" (excluding the input). The poster above you is likely referring to auxiliary space.

Re:Gaming CS Interviews by felixr on Wednesday September 28, 2022 @05:23AM (#33006041)
Sorry, wasn't clear. Was talking about the space complexity. If you sort in-place you don't need O(n) space, you can do with O(1 ). Not talking about time complexity
Re:Gaming CS Interviews by aliceryhl on Wednesday September 28, 2022 @06:13AM (#33006332)
They mean the amount of storage, and they're only counting additional memory allocated by the algorithm, and not the memory containing the input.
Re:Gaming CS Interviews by sfink on Wednesday September 28, 2022 @06:42AM (#33006496)
Well... sorting a shuffled deck of cards can be done in O(1) time.

    def sort(self):
        pass

    def __getitem__(i):
        suit = int(i / 13)
        rank = i % 13
        return f"{rank} of {('diamonds', 'hearts', 'spades', 'clubs')[suit]}"
Re:Gaming CS Interviews by tempodox on Wednesday September 28, 2022 @05:07AM (#33005936)
O(1) would mean same storage requirement regardless of element count.
Re:Gaming CS Interviews by felixr on Wednesday September 28, 2022 @05:28AM (#33006075)
Yes. Simplest in-place example would be bubble sort. You might need a temp element for swaps, but that's it. Heap sort can also be done with constant space. You need of course O(n) space to store the original data; but that is not part of the sort algorithm.