// measures the time a function needs

def time_needed[T](i: Int, code: => T) = {

  val start = System.nanoTime()

  for (j <- 1 to i) code

  val end = System.nanoTime()

  (end - start)/(i * 1.0e9)

}

for (i <- 1 to 10001 by 300) {

  val re = ("((a?){" + i + "})(a{" + i + "})")

  println(i + " " + "%.5f".format(time_needed(1, ("a" * i).matches(re))))  

}