CODEWITHSUNDEEP
rust
Pytan
Pytan

Reputation: 1684

chars().count() time complexity

I know str.len()'s time complexity is O(1). What about chars? Is the time complexity of str.chars().count() O(n) or O(1)?

Also, are there any sites about Rust time complexity like the one for Python?

Upvotes: 4

Views: 1195

Answers (1)

John Kugelman
John Kugelman

Reputation: 361947

Exhibit A

str.chars() returns a Chars iterator. Take a look at the documentation. There's something missing.

You'll notice that Chars does not implement the ExactSizeIterator trait. I'd expect it to implement that trait if getting the count were O(1).

Exhibit B

Scroll down to its implementation of Iterator::count and we see:

Consumes the iterator, counting the number of iterations and returning it.

Counting the number of iterations? That's not promising.

Exhibit C

Let's look at the source code, the ultimate source of truth. What do we find?

fn count(self) -> usize {
    // length in `char` is equal to the number of non-continuation bytes
    self.iter.filter(|&&byte| !utf8_is_cont_byte(byte)).count()
}

Iterate? Filter? Count? The final nail in the coffin.

Conclusion

Ladies and gentlemen, it's O(n). I rest my case!

Upvotes: 7

Related Questions