The Big O notation

In simple words, this notation is used to describe how fast an algorithm will run. It describes the growth of the algorithm's running time versus the size of input data.

Here is a simple example. Consider the following Scala snippet, reversing a linked list:

scala> def revList(list: List[Int]): List[Int] = list match { 
     |   case x :: xs => revList(xs) ++ List(x) 
     |   case Nil => Nil 
     | } 
revList: (list: List[Int])List[Int] 
scala> revList(List(1,2,3,4,5,6)) 
res0: List[Int] = List(6, 5, 4, 3, 2, 1) 

A quick question for you: how many times does the first case clause, namely case x :: xs => revList(xs) ++ List(x), match a list of six elements? Note that the clause matches when the list is non-empty. When it matches, we reduce the list by one element and recursively call the method.

It is easy to see the clause matches six times. As a result, the list method, ++, also gets invoked four times. The ++ method takes time and is directly proportional...