Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
student47
Group Title
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?)
 2 years ago
 2 years ago
student47 Group Title
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?)
 2 years ago
 2 years ago

This Question is Closed

maitre_kaio Group TitleBest ResponseYou've already chosen the best response.0
Which document are you taliking about ?
 2 years ago

student47 Group TitleBest ResponseYou've already chosen the best response.0
http://www.greenteapress.com/compmod/html/book003.html
 2 years ago

bwCA Group TitleBest ResponseYou've already chosen the best response.1
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/
 2 years ago

maitre_kaio Group TitleBest ResponseYou've already chosen the best response.0
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/
 2 years ago

maitre_kaio Group TitleBest ResponseYou've already chosen the best response.0
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.
 2 years ago

bwCA Group TitleBest ResponseYou've already chosen the best response.1
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
 2 years ago

maitre_kaio Group TitleBest ResponseYou've already chosen the best response.0
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)
 2 years ago

maitre_kaio Group TitleBest ResponseYou've already chosen the best response.0
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. :)
 2 years ago

maitre_kaio Group TitleBest ResponseYou've already chosen the best response.0
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/stringconcatenationvsstringsubstitutioninpython
 2 years ago

bwCA Group TitleBest ResponseYou've already chosen the best response.1
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
 2 years ago
See more questions >>>
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.