[Steven_Vellon]

In that case, you need to test if the memory is contiguous and copy to the new pointer if not. O(N^2) in the worst case, where every memory allocation returns a distinct start pointer.

What I was getting at is that in virtual memory the heap is always contiguous (even if it isn't in physical memory, but we only need it to be contiguous in virtual memory). So one can guarantee that the solution will never require copying data if the program exclusively uses the stack, and the resultant string is the only piece of data on the heap. You always add contiguous memory so your string can dynamically grow without ever copying to a new buffer. This probably requires allocating memory through the use of OS-specific syscalls to request new memory pages instead of malloc or realloc.

[termie]

Yes, the kernel will map virtual to physical however it sees fit, no guarantees there (at least not in user-space via glibc). Realloc will always return a virtually contiguous slice or NULL if it can’t. And you’re right, obviously all those potential subordinate mallocs would be inefficient. :) In this contrived FizzBuzz example case, you could pretty easily do the math and just malloc it all in one go at the start of the function. Fizz and Buzz are the same size, you would just need to add up the iota lengths and the trailing \0. If you take an arg for N (1..N) then stack allocations are not going to work. You need to statically declare their size.

[Steven_Vellon]

What I'm getting at, though, is that it's possible to implement it without any copies even if the memory consumption cannot be predetermined. Bypass malloc() and realloc() entirely and invoke brk() to increase the program's segment size. This grows the data segment contiguously (in virtual memory), so there will never be a need to copy the result string to a different buffer. In other words point the result pointer to the start of the heap, and never put anything else on the heap.

[unkulunkulu]

O(N) is worst if you realloc exponentially with O(N) worst case possible extra unused space in the end