On Fri, Feb 1, 2019 at 5:34 AM Grant Edwards <grant.b.edwa...@gmail.com> wrote: > > On 2019-01-31, Terry Reedy <tjre...@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 -- https://mail.python.org/mailman/listinfo/python-list
