Here's the question you clicked on:
student47
help.. on lecture 8. i am reading section 2.2 [Analysis of basic operations ] and i can't understand some phrases: If you use the same loop to “add” a list of strings, the run time is quadratic because string concatenation is linear.(why?), Sorting is O(n logn). (how?) , Most string and tuple operations are linear, except indexing and len, which are constant time.(why big O('len') operation is constant?)
Which document are you taliking about ?
hmmm: doesn't seem to be quadratic: http://dpaste.com/695468/ tried it with the word list from ps6, same result: http://dpaste.com/695475/
It is right: suppose you have an outer loop on a range of integers (like the one in the article). Now you have an inner loop on a list of strings. You want to concatenate the elements of this list. The size of the integer range is n, the size of the list of strings is m. Then you have n * m basic operations (here the basic operation is string concatenation, which is constant) Now, why does bwCA get a wrong result ? I must say that I don't fully understand his code as it's very idiomatic Python. But I can show you a program that demonstates this result: http://dpaste.com/hold/695547/
Most string and tuple operations are linear, except indexing and len, which are constant time: operations like min, max, sum require that you walmk through all the elements, hence are linear. What they call indexing is reading or writing elements: obviously constant time. len is constant, it may be surprising because you may think you have to count all the elements. But since it is a very often used operation, Python certainly does some kind of optimization, like updating a count each time the list is updated (trading space versus time) O(n log n) for the sort: probably the implementation is a merge sort (see lecture 10) What you're reading is very interesting because it shows that the real implementation may act differently from what we expect, and that the interpreter may optimize the code under the hood.
a classic quadratic algorithm is a loop within a loop. a single loop performing a constant operation is linear. so a linear operation performed in a loop should be quadratic. that book says string concatenation is linear so I initially thought that sounded correct - till i tried it. the code i i posted runs a function that adds strings together in a loop. it progressively doubles the number of strings added together and reports the execution time for each 'string addition loop' to complete. the results look linear to me (for number of strings being added together)- so something is amiss, probably my understanding or my implementation http://bayes.colorado.edu/PythonIdioms.html#idioms_efficient http://dpaste.com/695628/ shows that (just) adding two strings together is 'more than linear' with string size - at least on my computer
Ok I missed the point, so now I agree with student 47, why should string concatenation be linear ? No matter the size of the string, it should be constant time (and is imho)
I've just read your last piece of code. I think that when we're dealing with huge objects, there are too many factors that can lead to wrong interpretations (interpreter implementation, size of the memory, ...) so I still think that string concatenation should be considered a basic operation most of the time. But I'm still open to other arguments. :)
Ok I've messed it up ! I understand now why it should be linear: we have to take every character in the two strings and add it to the result, so it's linear in the length of the result... Sorry ! But the subject seems to be pretty complicated : http://stackoverflow.com/questions/376461/string-concatenation-vs-string-substitution-in-python
so how can we explain the seemingly linear behavior for the string concatenation loop timing experiment that i posted above? matbe things have changed since the book was written