CODEWITHSUNDEEP
scalascala-collections
Avenger
Avenger

Reputation: 877

What is the time complexity of sliding and grouped functions of list in scala

I am using sliding function of scala on a list and after drilling, it gives GroupedIterator.

I am wandering, what is the time complexity of funtions sliding and grouped?

val list = (1 to 10).toList

list.iterator.grouped(3).foreach(println(_))
list.grouped(11).foreach(println(_))
val st = (1 to 7).iterator.grouped(3).withPartial(false).toList
st
list.sliding(3).foreach(println(_))
list.sliding(11).foreach(println(_))


list.sliding(3,2).foreach(println(_))
list.sliding(11,2).foreach(println(_))

Seems grouped takes O(n) and sliding takes O(n*n).

Upvotes: 0

Views: 374

Answers (1)

Tim
Tim

Reputation: 27421

They are both O(n)

Grouped is clearly O(n) because it touches each element once.

Sliding is also O(n) because the number of times it touches each element is a constant. The fact that it touches the elements more than once does not affect the complexity.

Upvotes: 3

Related Questions