CODEWITHSUNDEEP
performancelispcommon-lispcomplexity-theorytime-complexity
flapas
flapas

Reputation: 583

Time complexity of list-length

I think list-length is a O(n) complexity operation, since it seems there's no other way to find it but going through all of the list's elements. 

;; iterates through list's elements
;; and returns 6, right?
(list-length '(1 2 3 4 5 6))

Nevertheless, I'd like to be sure, since it's critical for a work of mine. Is this correct?

Upvotes: 4

Views: 3718

Answers (3)

Broseph
Broseph

Reputation: 1773

Obviously, you can implement your own wrapper for regular lists that keeps track of how many elements have been added to it, and that would make finding it's length O(1).

Upvotes: 0

Joshua Taylor
Joshua Taylor

Reputation: 85883

The HyperSpec doesn't make a time constraint on list-length, but it does provide an implementation that runs in linear time. Since it can be implemented in linear time, it's hard to imagine why it wouldn't be.

It's worth noting, though, that depending on how cons cells are implemented, it might be possible to implement list-length in a way that list-length actually runs in O(n/k + k) time. (This is, of course, still O(n), but it doesn't necessarily go through all the lists elements.) For instance, if an implementation can get to a cddr without visiting the cdr (e.g., perhaps with some type of CDR coding?), then if it keeps a reference to the "current" cons as well as the previous one, it could get to the end of the list in n/2 time, and then check with one more reference whether the length of the list is n/2 or n/2 + 1. I only point this out to highlight the fact that list-length (or length, for that matter) might not need to "visit" each element of the list, if the implementation provides a way of skipping past an element.

Upvotes: 3

Rainer Joswig
Rainer Joswig

Reputation: 139346

Yes.

That's exactly right and I'm writing this sentence, because an answer needs at least 30 characters.

Upvotes: 11

Related Questions