Return to Revisions

As MichaelT explains in his answer, your code allocates O(n) strings. But it also allocates O(n²) bytes of memory and runs in O(n²) time.

It allocates O(n²) bytes, because the strings you're allocating have lengths 0, 1, 2, …, n-1, n, which sums to (n² - n) / 2 = O(n²).

The time is also O(n²), because allocating i-th string requires copying of (i-1)-th string, which has length i-1. This means each allocated byte has to be copied, which will take O(n²) time.

Maybe this is what the interviewers meant?