How to replace space in a string with \n

[Chris Angelico]

On Fri, Feb 1, 2019 at 5:34 AM 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.
>

Appending onto an immutable string means copying the entire string and
adding the new character.

(CPython does have an optimization that can sometimes improve this
specific case, but in general, this algorithm runs in quadratic time.)

ChrisA