Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

student47

  • 2 years ago

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?)

  • This Question is Closed
  1. maitre_kaio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Which document are you taliking about ?

  2. student47
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    http://www.greenteapress.com/compmod/html/book003.html

  3. bwCA
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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/

  4. maitre_kaio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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/

  5. maitre_kaio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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.

  6. bwCA
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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

  7. maitre_kaio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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)

  8. maitre_kaio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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. :)

  9. maitre_kaio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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/string-concatenation-vs-string-substitution-in-python

  10. bwCA
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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

  11. Not the answer you are looking for?
    Search for more explanations.

    Search OpenStudy
    • Attachments:

Ask your own question

Ask a Question
Find more explanations on OpenStudy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.