4 ms·
For 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
by mumblemumble 5y ago
For 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.