3 ms·

There is CS61A for that, not even a specialized course of algorithms and data-structures.) Lists, being an "asymmetrical" recursive data structure, have O(1) t

There is CS61A for that, not even a specialized course of algorithms and data-structures.) Lists, being an "asymmetrical" recursive data structure, have O(1) time for adding an element to its head but O(n) time for sticking an element to its tail, and a search (for membership) would be O(n) in the worst case. Keeping the list pre-sorted would save some time. In case one needs a quick (close to O(1)) look-up there are hash-tables. It is even funny to see that it comes as a surprise.) As Brian Harvey explicitly mentioned few times, constant factors doesn't matter, while choosing appropriate data-structure could make a dramatic changes, such as changing form a linear time to near constant. Another topic is about using non-memoized recursion, like in the classic case of a naive recursive function of computing Fibonacci numbers. That is another proof that taking a decent introductory CS course (preferably, based on SICP) is the must for any person who for some reason decided to code.

stiff 13y ago
I agree with your overall sentiment, but I have some objections with the specific things you are saying: - SICP the book and the original MIT course that is available online do not cover data structures or algorithms very well, it isn't that much in the focus of the book, they implement a queue in one place from what I remember, there is some mention of big-oh, but it's all rather cursory. Thomas Cormen published "Algorithms Unlocked" recently, which seems like a good intro book for programmers who are not willing to devote a fraction of their life to studying the big Cormen book or Knuth. - Constant factors matter increasingly more and more. There has been a lot of talk in the last years about how things like big and very fast processor caches make some not-asymptotically optimal algorithms outperform the asymptotically optimal ones for all input sizes we can ever expect to handle. One should of course still understand asymptotic analysis, but you also have to understand caches, locality of reference and do real-world benchmarking. One doesn't substitute the other.
- dschiptsov 13y ago
  There is a wonderful set of lectures by the two magicians.) I used to watch some before going to bed. Actually it takes a long time to understand what they are saying (big ideas behind the words) and why they chose so (why this or that particular example). But the great idea is quite simple: "All you need is Lambda and the List structure as a glue (to create layers of DSLs) plus self-discipline of not violating abstraction barriers". But one has to really understand them. (Well, arrays and hash-tables are also necessary due to some efficient algorithms based on its unique properties).
icebraining 13y ago
Lists, being an "asymmetrical" recursive data structure, have O(1) time for adding an element to its head but O(n) time for sticking an element to its tail Well, a list is an abstract data structure. Being Python, it's implemented as an array, so adding an element to the head actually costs O(n) - since all elements must be copied to the next position - while appending to the tail is O(1) (amortized, since in certain cases it triggers a full resize, requiring a full new copy of the list). The language wiki has a page with the time complexity of a few of its data structures: https://wiki.python.org/moin/TimeComplexity https://wiki.python.org/moin/TimeComplexity
- eru 13y ago
  Thanks for the insight. By the way, you could make Python's list's adding of one element at the back worst case O(1), too, if you were willing to waste some space.
- dschiptsov 13y ago
  Yes, my inaccuracy - I considered them from the classic Lisps point of view. The trade-offs they made in Python about list's implementation are disputable.)

stiff 13y ago

I agree with your overall sentiment, but I have some objections with the specific things you are saying: - SICP the book and the original MIT course that is available online do not cover data structures or algorithms very well, it isn't that much in the focus of the book, they implement a queue in one place from what I remember, there is some mention of big-oh, but it's all rather cursory. Thomas Cormen published "Algorithms Unlocked" recently, which seems like a good intro book for programmers who are not willing to devote a fraction of their life to studying the big Cormen book or Knuth. - Constant factors matter increasingly more and more. There has been a lot of talk in the last years about how things like big and very fast processor caches make some not-asymptotically optimal algorithms outperform the asymptotically optimal ones for all input sizes we can ever expect to handle. One should of course still understand asymptotic analysis, but you also have to understand caches, locality of reference and do real-world benchmarking. One doesn't substitute the other.

dschiptsov 13y ago
There is a wonderful set of lectures by the two magicians.) I used to watch some before going to bed. Actually it takes a long time to understand what they are saying (big ideas behind the words) and why they chose so (why this or that particular example). But the great idea is quite simple: "All you need is Lambda and the List structure as a glue (to create layers of DSLs) plus self-discipline of not violating abstraction barriers". But one has to really understand them. (Well, arrays and hash-tables are also necessary due to some efficient algorithms based on its unique properties).

icebraining 13y ago

Lists, being an "asymmetrical" recursive data structure, have O(1) time for adding an element to its head but O(n) time for sticking an element to its tail Well, a list is an abstract data structure. Being Python, it's implemented as an array, so adding an element to the head actually costs O(n) - since all elements must be copied to the next position - while appending to the tail is O(1) (amortized, since in certain cases it triggers a full resize, requiring a full new copy of the list). The language wiki has a page with the time complexity of a few of its data structures: https://wiki.python.org/moin/TimeComplexity https://wiki.python.org/moin/TimeComplexity

eru 13y ago
Thanks for the insight. By the way, you could make Python's list's adding of one element at the back worst case O(1), too, if you were willing to waste some space.
dschiptsov 13y ago
Yes, my inaccuracy - I considered them from the classic Lisps point of view. The trade-offs they made in Python about list's implementation are disputable.)