> How is making a returning a new dynamic array worse than doing a O(n^2) implementation Avoiding unnecessary allocations can easily mean the difference betwee

> How is making a returning a new dynamic array worse than doing a O(n^2) implementation Avoiding unnecessary allocations can easily mean the difference between missing a frame and not. Keep in mind that we frequently have to deal with bad mallocs and OSes/hardware without virtual memory capabilities. The main reason I'd prefer O(n^2) vs O(n)+allocation is that I asked for an in-place solution, and there are definitely situations where you'd need to be able to do this (because of pointers to the array base, or because the caller doesn't have access to the allocator to release it, or you're using an arena and then allocating a new array means wasting the memory of the old one...). Another reason that's a bit more subtle is that the O(n^2) is that it's much more likely to show up when profiling, unlike the allocation which will likely just make everything else slightly slower due to fragmentation.