3 ms·
> For grabbing individual elements, cadddr and friends are O(N) for linked lists That doesn't really make sense. cadddr is O(1), and so are all its c[ad]{1,4}r
by jhgb 5y ago
> For grabbing individual elements, cadddr and friends are O(N) for linked lists
That doesn't really make sense. cadddr is O(1), and so are all its c[ad]{1,4}r friends.
> For what it's worth, I find I never program that way in Clojure.
I suspect you don't do that because the language doesn't support it well. Which is fine, since going against the grain of a language is generally inadvisable, but it says nothing about the technique in itself.
- mumblemumble 5y agoFor a linked list implementation, car requires traversing one cons cell, cadr requires traversing two, caddr three, four for cadddr, and so on. That's about as textbook an example of O(N) as you can get.
- jhgb 5y agoBut your N is bounded from above to 4, so pretty much anything using these functions won't be unbounded in time just because of use of these functions. If you're suggesting that using nth or elt on a list of arbitrary length is a bad idea, then yes, it is, but I certainly wasn't suggesting that.