CODEWITHSUNDEEP
rust
kevlarr
kevlarr

Reputation: 1162

What is the runtime complexity of Vec::len?

Given a vector...

let v = vec![1, 2, 3, 4, 5];

Is calling v.len() O(1) or O(n)?

Neither "The Book" (from what I can tell so far) nor the docs mention whether .len() is constant time or not, and I cannot find anything on Stack Overflow or elsewhere.

I'm assuming it's O(1) since [], .push(), and .pop() all are, but I want to be sure before I litter my code with v.len().

I know that I can easily just store/reference the return of len but in some situations - like inner functions - I don't want to keep having to pass both a vector and an int around.

Thanks to @Stargateur for pointing out that indexing's O(1) is different from push/pop's amortized O(1)

Upvotes: 14

Views: 2085

Answers (1)

Yury Tarabanko
Yury Tarabanko

Reputation: 45106

It is O(1) as of the implemented code in Rust 1.25.0:

pub fn len(&self) -> usize {
    self.len
}

Upvotes: 16

Related Questions