What is time complexity of slice in scala? -

What is time complexity of slice in scala? -

what time complexity of scala piece method? o(m) or o(n), m number of elements in piece , n number of elements in collection.

more specific question: time complexity of somemap.slice(i, + 1).keys.head, random int less somemap.size? if piece complexity o(m) should o(1), right?

this depends on underlying datatype. slicing array, arraybuffer, bytebuffer, or other sub-class of indexedseqoptimized illustration o(1). list, example, o(n) can see implementation. you'll want check source specific type.

map gets implementation of piece iterablelike. implementation pasted below, it's cost iterate on elements in collection plus cost create newly built map.

for treemap should o(n + k lg k) if you're slicing k elements out of map.

for hashmap should bounded o(n).

override /*traversablelike*/ def slice(from: int, until: int): repr = { val lo = math.max(from, 0) val elems = until - lo val b = newbuilder if (elems <= 0) b.result() else { b.sizehintbounded(elems, this) var = 0 val = iterator drop lo while (i < elems && it.hasnext) { b += it.next += 1 } b.result() } }

when in doubt, @ source.

scala