Geek Answers Handbook

What is the runtime for size on a Scala ListBuffer?

Is it constant or O (n)? If O (n) have similar data structures with constant time-size operations?

+4
source share
1 answer

Oddly, size and length have different descriptions in ListBuffer Docs . Of course, ListBuffer.length is a constant time. Prior to Scala 2.8, length really was O (n), but now it is now fixed . the implementation of size in TraversableOnce suggests that it is O (n), but I can skip something.

Other performance characteristics of the Scala collections are described here . For ListBuffer in particular,

  head tail apply update prepend append insert ListBuffer CLLLCCL

where C is constant and L is linear time.

Edit: both the length and size of the ListBuffer is now O (1). The issue mentioned by @KiptonBarros was closed with Scala 2.9.1: <a4>

+3
source

More articles:


All Articles