Mekire: Re-adding some good discussion we had on the original thread.
Very nice. I wouldn't mind a follow up tutorial that went into more depth on the common time complexities encountered. I still, for instance, find correctly identifying O(nlogn) to be tricky.
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?
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):
Whereas the less intuitive:
-Mek
Very nice. I wouldn't mind a follow up tutorial that went into more depth on the common time complexities encountered. I still, for instance, find correctly identifying O(nlogn) to be tricky.
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?
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)+1performs in O(n).
-Mek