On 1/31/2019 1:36 PM, Grant Edwards wrote:
On 2019-01-31, 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.
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
--
https://mail.python.org/mailman/listinfo/python-list
