3 ms·
Finding the last element in a vector is initially given as theoretical complecity O(n) -- What? In any language I used, a vector would have information about ho
by zelphirkalt 4y ago
Finding the last element in a vector is initially given as theoretical complecity O(n) -- What? In any language I used, a vector would have information about how long it is and that would be used to get an index (length - 1) and the access is constant O(1).
Not sure what kind of vectors are assumed in the article.
- dreamcompiler 4y agoI had the same reaction. The only O(n) case I can think of is C's zero-delimited strings. But does anybody even still use these things nowadays?
- TingPing 4y agoMillions of C projects, yes.
- bhuber 4y agoOn any sort of list structure, a "find" operation generally means searching the list in order for an element that satisfies a predicate, usually equality to a given value. The article could be more clear about this, but in this context finding the last element in a list means calling find() on a list where only the last element of the list matches the predicate. This is almost the worst case scenario (the worst case being no elements in the list match). If you read the code in the article, you can see it's using https://www.cplusplus.com/reference/algorithm/find/ https://www.cplusplus.com/reference/algorithm/find/ to find an element in the list of value 1, after inserting that as the last element in the list. The point is, it doesn't matter if you know the length of the list, you still have to examine all the elements.