How to replace space in a string with \n

[Terry Reedy]

On 1/31/2019 1:36 PM, Grant Edwards wrote:
> On 2019-01-31, Grant Edwards <grant.b.edwards at gmail.com> wrote:
>> On 2019-01-31, Terry Reedy <tjreedy at udel.edu> wrote:
>>> On 1/31/2019 11:19 AM, Ian Clark wrote:
>>>> text = "The best day of my life!"
>>>> output = ''
>>>>
>>>> for i in text:
>>>>    if i == ' ':
>>>>     output +='\n'
>>>>    else:
>>>>     output += i
>>>>
>>>> print(output)
>>
>>> But this is an awful, O(n*n) way to solve an inherently O(n) problem,
>>
>> How is it O(n^2)?
>>
>> It loops through the input sequence exactly once.  That looks like
>> O(n) to me.
> 
> Doh!
> 
> The 'output +=' operation is also O(n), and it's executed n times.

It is like bubble sort doing n x O(n) operations.  This does not mean 
that O(n*n) is always bad as it may beat O(n*logn) or even O(n) in terms 
of real time when the neglected multiplier and other terms are 
considered*. I regularly write use + to catenate a few, fixed number of 
terms.  But I just read a blogger who used += in a loop like the above 
where there could also be 1000s or more strings to be added together.

* timsort (Tim Peters), used for list.sort and other language sorts, 
uses 'O(n*n)' binary insert sort for 'short' subarrays.  Tim empirically 
selected 64 as the boundary between 'short' and 'long' for Python.  On 
modern CPUs, the O(n*n), shifting part of an array, is done (relatively 
fast) with a single machine instruction.

-- 
Terry Jan Reedy