Complexities and collections

Let's look at collections and see how complexity helps us to see how they will perform in different situations. We will look at commonly used collections and idioms.

The sliding window

The sliding method allows us to create a sliding window. Here's an example:

scala> val list = List(1,2,3,4,5,6) 
list: List[Int] = List(1, 2, 3, 4, 5, 6) 
 
scala> val list1 = list.sliding(2,1).toList 
list1: List[List[Int]] = List(List(1, 2), List(2, 3), List(3, 4), List(4, 5), List(5, 6)) 

This creates List[Int]. Each element of List contains the current element and its successor in the original list.

Here is the equivalent code in Clojure:

user=> (partition 2 1 '(1 2 3 4 5 6)) 
((1 2) (2 3) (3 4) (4 5) (5 6)) 

It gives us similar results:

Let's see the complexity of this sliding window code. The time complexity is O(n). We need to visit each element of the original list twice: once when it is the first element, and second, when it is the second element. This is clearly...