CODEWITHSUNDEEP
scalacomplexity-theoryscala-collections
deltanovember
deltanovember

Reputation: 44051

In Scala, what is the running time of trimStart and trimEnd for ListBuffer?

Suppose I'm only removing a single element. I would like these methods to implement a fixed size ListBuffer. I would only use if they run in O(1) time. The documentation is slightly ambiguous does anybody know the implementation details?

Upvotes: 3

Views: 495

Answers (1)

Jean-Philippe Pellet
Jean-Philippe Pellet

Reputation: 59994

The relevant implementation is there (for ListBuffer) and there (for BufferLike).

trimStart(n) is linear with respect to n (so, constant if you remove a single element); trimEnd(n) is linear with respect to the size of the collection.

Apart from that, I fail to see how you want to have a fixed-size ListBuffer on which you change the size with such trim methods…

Upvotes: 6

Related Questions