Efficiency Crash Course

[micseydel]

Mekire: Re-adding some good discussion we had on the original thread.

Thank you for the comments Mek. Apologies on taking so long to reply, I hadn't read your comments yet and was going to reply and also duplicate the efforts you mention below (which I now won't).

I still, for instance, find correctly identifying O(nlogn) to be tricky.

Since things are usually related to loops, you can look at it in terms of multiplying the number of iterations by the time each iteration takes. An O(n log n) sorting algorithm for example is either going to iterate n times, doing log n work each time, or else will iterate log n times and each iteration do n work. I tried to make this as brief as possible yet still get a basis, I realize it's not exhaustive. I want to make sure it's short enough that people will actually read it haha. We could start a series on it though.

On the point of your example, using string concatenation does, as you alluded to, sometimes make it hard to see these results in the wild.  You could go into more detail with it here, but I think perhaps this past thread might suffice:
Time complexity different between operating systems. Why?

Thanks for the link to that thread, it's probably adequate. I was going to waste time elaborating but now I don't have to  :)
I would mention though that you can verify it empirically by creating a dummy variable on the string which would have been modified in-place, since Python won't modify the string if there is more than one reference to it. Perhaps a small code sample is worth it, or it could be left as an exercise to the reader as so many of students' favorite textbooks tend to do ;)

I tend to use examples with the list.count() builtin vs dictionary counting (or using collections.Counter) to illustrate the quadratic vs linear time of counting items in a large sequence.

I for instance have often seen people do things like this (and think themselves very clever):

count_items = {item:items.count(item) for item in items}

Not realizing that this is O(n^2).

Whereas the less intuitive:

count_items = {}
for item in items:
    count_items[item] = count_items.get(item, 0)+1

performs in O(n).

-Mek

I think this is a wonderful example. Do you think this should be incorporated? Left as a comment here? Part of another thread?