// 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))))  
}