How to replace space in a string with \n
Terry Reedy
tjreedy at udel.edu
Thu Jan 31 18:05:50 EST 2019
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
More information about the Python-list
mailing list