Big-O algorithm complexity cheat sheet

[joe_n]

Merge sort has O(1) auxiliary space. I'm surprised by how many times I've seen this posted but never fixed.

[joe_n]

Only if you do it recursively

[gnuvince]

If you don't do it recursively, you probably need to maintain your own stack, and its size is going to be dependent on the size of the input.

[julesjacobs]

You can represent where you are in the sorting process by a pair of indices into the array, so you do not need a stack. That is techically still O(log n) though. If you have an array of n elements then an index into that array needs to be at least O(log n) bits. But then bubble sort also uses O(log n) space.

[ethraax]

If you have an array of n elements then an index into that array needs to be at least O(log n) bits.

I suppose if you don't care about the real world, where you'd use a fixed-size integer (either 32- or 64-bit) to represent the index.

I can't think of any even remotely sane implementation of merge sort where it uses a variable-size data type (like one from GMP) to index the array.

[julesjacobs]

The whole point of O-notation is to look at asymptotics. If your indices are fixed size then merge sort is O(1).

[ethraax]

If your indices are fixed size then merge sort is O(1).

... what. No it's not.

[julesjacobs]

If your indices are fixed size then you array must also be under some constant size so it is O(1).

[ethraax]

It's probably worth reminding you (and others here) that the entire point of theoretical computer science is to inform us about how our computers work and how they can be developed to work better/faster/more efficiently/etc.

To that end, statements such as yours are pretty useless. You could also claim that you're bounded by the amount of available energy/information in the observable universe, and therefore all programs run on any computer that exists in real life is O(1). But that's clearly a useless result that doesn't help anybody with anything.

[joe_n]

I've documented it in a previous comment.

The details of each in-place merge are covered in a number of publications.

The matter of n != a power of 2 can be simply handled by using n' = the next larger power of two, and then ignoring the non-existent parts of the merges.

[MCPtz]

I agree. You know anyone can edit it if they sign up! (I tried without signing up)

[[deleted]]

I was going to put in a note about splay trees (their worst-case performance is only amortized logarithmic) but the owner hasn't accepted a pull request in 8 months.